# Constructing Minimally 3-Connected Graphs
## 5 Isomorph-Free Graph Construction
### Infinite Bookshelf Algorithm
First, for any vertex \(a\) adjacent to \(b\) other than \(c\), \(d\), or \(y\), for which there are no \(c-a\), \(c-b\), \(d-b\), or \(d-a\) chording paths in \(G\backslash\{ab,by,cy,dy\}\), we split \(b\) to add a new vertex \(x\) adjacent to \(b\), \(a\) and \(y\). This is the same as the third step illustrated in Figure 7.  
Second, for any pair of vertices \(a\) and \(k\) adjacent to \(b\) other than \(c\), \(d\), or \(y\), and for which there are no \(k-a\) or \(k-b\) chording paths in \(G\backslash\{ab,by,cy,dy\}\), we split \(b\) to add a new vertex \(x\) adjacent to \(b\), \(a\) and \(k\) (leaving \(y\) adjacent to \(b\), unlike in the first step). Since C2 must make \(\mathcal{O}(n^{2})\) calls to ApplyFlipEdge, where \(n=|V(G)|\), its complexity is \(\mathcal{O}(|\mathcal{C}|^{2}n^{3})\). Pseudocode is shown in Algorithm 6. ```
1:procedureC2(\(G,\mathcal{C},c,b,d,y\))
2:\(S\leftarrow\phi\)
3:for\(a\in N(b)\backslash\{c,d,y\}\)do\(\triangleright\) Final step of Operation (c)
4:ifNoChordingPaths(\(\mathcal{C},G,\{(c,a),(c,b),(d,b),(d,a)\},\{ab,by,cy,dy\}\)) then
5:\(G^{\prime},x\leftarrow\textsc{SplitVertex}(G,b,y,a)\)
6:\(\mathcal{C}^{\prime}\leftarrow\textsc{ApplySubdivideEdge}(\mathcal{C},b,a,x)\)
7:\(\mathcal{C}^{\prime\prime}\leftarrow\textsc{ApplyFlipEdge}(\mathcal{C}^{ \prime},y,b,x)\)
8:\(S\gets S\cup\{(G^{\prime},\mathcal{C}^{\prime\prime})\}\)
9:endif
10:endfor
11:for\(a,k\in N(b)\backslash\{c,d,y\}\)do\(\triangleright\) Final step of Operation (d)
12:ifNoChordingPaths(\(\mathcal{C},G,\{(k,a),(k,b)\},\{ab,by,cy,dy\}\)) then
13:\(G^{\prime},x\leftarrow\textsc{SplitVertex}(G,b,k,a)\)
14:\(\mathcal{C}^{\prime}\leftarrow\textsc{ApplySubdivideEdge}(\mathcal{C},b,a,x)\)
15:\(\mathcal{C}^{\prime\prime}\leftarrow\textsc{ApplyFlipEdge}(\mathcal{C}^{ \prime},k,b,x)\)
16:\(S\gets S\cup\{(G^{\prime},\mathcal{C}^{\prime\prime})\}\)
17:endif
18:endfor
19:return\(S\)
20:endprocedure
```  
**Algorithm 6** Second vertex split procedure  
Procedure C3 is responsible for implementing the third step in operation D3, as illustrated in Figure 8. It starts with a graph \(G=H+\{e_{1},e_{2}\}\) generated by E2, where \(e_{1}=xy\) and \(e_{2}=xz\) are two incident edges. A single new graph is generated in which \(x\) is split to add a new vertex \(w\) adjacent to \(x\), \(y\) and \(z\), if there are no \(x-y\), \(x-z\), or \(y-z\) chording paths in \(G\backslash\{xy,xz\}=H\). Because C3 makes one call to ApplyFlipEdge, its complexity is \(\mathcal{O}(|\mathcal{C}|^{2}n)\). Pseudocode is shown in Algorithm 7. ```
1:procedureC3(\(G,\mathcal{C},x,y,z\))
2:\(S\leftarrow\phi\)
3:ifNoChordingPaths(\(\mathcal{C},G,\{(x,y),(x,z),(y,z)\},\{xy,xz\}\)) then
4:\(G^{\prime},w\leftarrow\textsc{SplitVertex}(G,x,y,z)\)
5:\(\mathcal{C}^{\prime}\leftarrow\textsc{ApplySubdivideEdge}(\mathcal{C},x,z,w)\)
6:\(\mathcal{C}^{\prime}\leftarrow\textsc{ApplyFlipEdge}(\mathcal{C}^{ \prime},y,x,w)\)
7:\(S\leftarrow S\cup\{(G^{\prime},\mathcal{C}^{\prime})\}\)
8:endif
9:return\(S\)
10:endprocedure
```  
**Algorithm 7** Third vertex split procedure  
Procedure C3 is responsible for implementing the third step in operation D3, as illustrated in Figure 8. It starts with a graph \(G=H+\{e_{1},e_{2}\}\) generated by E2, where \(e_{1}=xy\) and \(e_{2}=xz\) are two incident edges. A single new graph is generated in which \(x\) is split to add a new vertex \(w\) adjacent to \(x\), \(y\) and \(z\), if there are no \(x-y\), \(x-z\), or \(y-z\) chording paths in \(G\backslash\{xy,xz\}=H\). Because C3 makes one call to ApplyFlipEdge, its complexity is \(\mathcal{O}(|\mathcal{C}|^{2}n)\). Pseudocode is shown in Algorithm 7.