# Constructing Minimally 3-Connected Graphs
## 5 Isomorph-Free Graph Construction
### Infinite Bookshelf Algorithm
```
1:procedureE2(\(G\), \(u\), \(v\), \(\mathcal{C}\))
2:\(S\leftarrow\phi\)
3:for\(w\in V(G)\)do
4:if\(wu\
otin E(G)\)then
5:\(G^{\prime}\leftarrow\textsc{AddEDGE}(G,u,w)\)
6:\(\mathcal{C}^{\prime}\leftarrow\textsc{ApplyAdDEDGE}(\mathcal{C},u,w)\)
7:\(S\gets S\cup\{(G^{\prime},\mathcal{C}^{\prime},uw)\}\)
8:endif
9:if\(wv\
otin E(G)\)then
10:\(G^{\prime}\leftarrow\textsc{AddEDGE}(G,w,v)\)
11:\(\mathcal{C}^{\prime}\leftarrow\textsc{ApplyAdDEDGE}(\mathcal{C},w,v)\)
12:\(S\gets S\cup\{(G^{\prime},\mathcal{C}^{\prime},wv)\}\)
13:endif
14:endfor
15:return\(S\)
16:endprocedure
```  
**Algorithm 4** Second edge addition procedure Procedure C1 is responsible for implementing the second step of operations D1 and D2. These steps are illustrated in Figures 6 and 7, respectively, though a bit of bookkeeping is required to see how C1 corresponds to those operations. C1 starts with a graph \(G=H+e\) generated by E1; let \(bc\) denote the added edge. Observe that the chording path checks are made in \(H\), which is \(G\backslash bc\). First, for any vertex \(a\in N(b)\backslash c\) in \(G\), where there are no chording \(c-a\) or \(b-c\) paths in \(G\backslash\{bc,ba\}=H\backslash ba\), we split \(b\) to add a new vertex \(x\) adjacent to \(a\), \(b\), and \(c\). This is the same as the second step illustrated in Figure 6 with \(c\), \(b\), \(a\), and \(x\) in C1 corresponding to \(x\), \(a\), \(b\), and \(y\) in the figure, respectively. It is also the same as the second step illustrated in Figure 7, with \(c\), \(b\), \(a\), and \(x\) in C1 corresponding to \(b\), \(c\), \(d\), and \(y\) in the figure, respectively. Second, we must consider splits of the other end vertex of the newly added edge \(e\), namely \(c\). For any vertex \(d\in N(c)\backslash b\) in \(G\) where there are no chording \(b-d\) or \(b-c\) paths in \(G\backslash\{bc,cd\}=H\backslash cd\), we split \(c\) to add a new vertex \(y\) adjacent to \(b\), \(c\), and \(d\). This is the same as the second step illustrated in Figure 6 with \(b\), \(c\), \(d\), and \(y\) in C1 corresponding to \(x\), \(a\), \(b\), and \(y\) in the figure, respectively. It is also the same as the second step illustrated in Figure 7, with \(b\), \(c\), \(d\), and \(y\) in C1 corresponding to \(b\), \(c\), \(d\), and \(y\) in the figure, respectively. Since C1 must make \(\mathcal{O}(n)\) calls to ApplyFlipEdge, where \(n=|V(G)|\), its complexity is \(\mathcal{O}(|\mathcal{C}|^{2}n^{2})\). Pseudocode is shown in Algorithm 5. ```
1:procedureC1(\(G\), \(b\), \(c\), \(\mathcal{C}\))
2:\(S\leftarrow\phi\)
3:for\(a\in N(b)\backslash c\)do\(\triangleright\) Split \(b\)
4:ifNoChordingPaths\((\mathcal{C},G,\{(c,a),(b,c)\},\{bc,ba\})\)then
5:\(G^{\prime},x\leftarrow\textsc{SplitVertex}(G,b,c,a)\)
6:\(\mathcal{C}^{\prime}\leftarrow\textsc{ApplySubdivideEdge}(\mathcal{C},b,c,x)\)
7:\(\mathcal{C}^{\prime}\leftarrow\textsc{ApplyFlipEdge}(\mathcal{C}^{\prime},a,b,x)\)
8:\(S\gets S\cup\{(G^{\prime},\mathcal{C}^{\prime},b,c,a,x)\}\)
9:endif
10:endfor
11:for\(d\in N(c)\backslash b\)do\(\triangleright\) Split \(c\)
12:ifNoChordingPaths\((\mathcal{C},G,\{(b,d),(c,b)\},\{bc,cd\})\)then
13:\(G^{\prime},y\leftarrow\textsc{SplitVertex}(G,c,b,d)\)
14:\(\mathcal{C}^{\prime}\leftarrow\textsc{ApplySubdivideEdge}(\mathcal{C},c,b,y)\)
15:\(\mathcal{C}^{\prime}\leftarrow\textsc{ApplyFlipEdge}(\mathcal{C}^{\prime},d,c,y)\)
16:\(S\gets S\cup\{(G^{\prime},\mathcal{C}^{\prime},c,b,d,y)\}\)
17:endif
18:endfor
19:return\(S\)
20:endprocedure
```  
**Algorithm 5** First vertex split procedure  
Procedure C2 is responsible for implementing the third step in operation D2, as illustrated in Figure 7. It starts with a graph \(G=(H+e)\circ f\) generated by C1; we denote \(e^{\prime}\) and \(f\) shown in the figure as \(yb\) and \(yc\), respectively. \(d\) represents the third vertex that becomes adjacent to the new vertex in C1, so \(d\) and \(y\) are also adjacent.