# Constructing Minimally 3-Connected Graphs
## 5 Isomorph-Free Graph Construction
### Infinite Bookshelf Algorithm  
This subsection contains a detailed description of the algorithms used to generate graphs, implementing the process described in Section 5.2. The process of computing \((G+e)\circ f_{c}\), \((G+e)\circ\{f_{c},f_{b}\}\), and \((G+\{e_{1},e_{2}\})\circ f\) is broken down into individual procedures E1, E2, C1, C2, and C3, each of which operates on an input graph with one less edge, or one less edge and one less vertex, than the graphs it produces. The procedures are implemented using the following component steps, as illustrated in Figure 13:  
* Procedure E1 is applied to graphs in \(A_{m-1,n}^{(*)}\), which are minimally 3-connected, to generate all possible single edge additions \(G+e\) given an input graph \(G\). This is the first step for operations D1, D2, and D3, as expressed in Theorem 8. The cycles of the output graphs are constructed from the cycles of the input graph \(G\) (which are  
Figure 15: Graph generation steps. carried forward from earlier computations) using ApplyAddEdge. The results, after checking certificates, are added to \(B_{m,n}\). * Procedure E2 is applied to graphs in \(B_{m-1,n}\) and treats an input graph as \(G+e_{1}\) in operation D3, as expressed in Theorem 8. It adds all possible edges with a vertex in common to the edge added by E1 to yield a graph \(G+\{e_{1},e_{2}\}\). This is the second step in operation D3 as expressed in Theorem 8. Cycles in these graphs are also constructed using ApplyAddEdge. The results, after checking certificates, are added to \(C_{m,n}\). * Procedure C1 is applied to graphs in \(B_{m-1,n-1}\) and treats an input graph as \(G+e\) as defined in operations D1 and D2, as expressed in Theorem 8. It generates two splits \((G+e)\circ f\) for each input graph, one for each of the vertices incident to the edge added by E1. This is the second step in operations D1 and D2, and it is the final step in D1. It uses ApplySubdivideEdge and ApplyFlipEdge to propagate cycles through the vertex split. The results, after checking certificates, are added to \(A^{(1)}_{m,n}\). This procedure only produces splits for graphs for which the original set of vertices and edges is 3-compatible, and as a result it yields only minimally 3-connected graphs. * Procedure C2 is applied to graphs in \(A^{(1)}_{m-1,n-1}\) and treats an input graph as \((G+e)\circ f_{c}\) as defined in operation D2, as expressed in Theorem 8. It generates splits \((G+e)\circ\{f_{c},f_{b}\}\) of the remaining un-split vertex incident to the edge added by E1. This is the third step of operation D2 when the new vertex is incident with \(e\); otherwise it comprises another application of D1. It uses ApplySubdivideEdge and ApplyFlipEdge to propagate cycles through the vertex split. The results, after checking certificates, are added to \(A^{(2)}_{m,n}\). This procedure only produces splits for 3-compatible input sets, and as a result it yields only minimally 3-connected graphs. * Procedure C3 is applied to graphs in \(C_{m-1,n-1}\) and treats an input graph as \(G+\{e_{1},e_{2}\}\) as defined in operation D3 as expressed in Theorem 8. For each input graph, it generates one vertex split \((G+\{e_{1},e_{2}\})\circ f\) of the vertex common to the edges added by E1 and E2. It uses ApplySubdivideEdge and ApplyFlipEdge to propagate cycles through the vertex split. The results, after checking certificates, are added to \(A^{(3)}_{m,n}\). This procedure only produces splits for 3-compatible input sets, and as a result it yields only minimally 3-connected graphs. While C1, C2, and C3 produce only minimally 3-connected graphs, they may produce different graphs that are isomorphic to one another. We use [PERSON]'s nauty to generate a canonical label for each graph produced, so that only pairwise non-isomorphic sets of minimally 3-connected graphs are ultimately output.