# Constructing Minimally 3-Connected Graphs
## 5 Isomorph-Free Graph Construction
### Infinite Bookshelf Algorithm
The following procedures are defined informally:  
* \(\textsc{AddEdge}(G,u,v)\)--Given a graph \(G\) and a pair of vertices \(u\) and \(v\) in \(G\), this procedure returns a graph \(G^{\prime}\) formed from \(G\) by adding an edge connecting \(u\) and \(v\). When it is used in the procedures in this section, we also use ApplyAddEdge immediately afterwards, which computes the cycles of the graph with the added edge. The complexity of AddEdge is \(\mathcal{O}(n^{2})\) because the set of edges of \(G\) must be copied to form the set of edges of \(G^{\prime}\). * \(\textsc{SplitVertex}(G,v,u,w)\)--Given a graph \(G\), a vertex \(v\) and two edges \(vu\) and \(vw\), this procedure returns a graph \(G^{\prime}\) formed from \(G\) by adding a vertex \(v^{\prime}\), adding an edge connecting \(v\) and \(v^{\prime}\), and replacing the edges \(vu\) and \(vw\) with edges \(v^{\prime}u\) and \(v^{\prime}w\). When it is used in the procedures in this section, we also use ApplySubdivideEdge and ApplyFlipEdge, which compute the cycles of the graph with the split vertex. The complexity of SplitVertex is \(\mathcal{O}(n^{2})\), again because a copy of the graph must be produced. * \(\textsc{NoChordingPaths}(\mathcal{C},G,P,X)\)--Given the set \(\mathcal{C}\) of cycles of a graph \(G\), a set \(P\) of pairs of vertices and another set \(X\) of edges, this procedure determines whether there are any chording paths connecting pairs of vertices in \(P\) in \(G\backslash X\). Its complexity is \(\mathcal{O}(|\mathcal{C}|n^{3})\), as it requires all simple paths between two vertices to be enumerated, which is \(\mathcal{O}(n^{2})\). This function relies on HasChordingPath as defined in Section 3. The rest of this subsection contains a detailed description and pseudocode for procedures E1, E2, C1, C2 and C3. The worst-case complexity for any individual procedure in this process is the complexity of C2: \(\mathcal{O}(|\mathcal{C}|^{2}n^{3})\). Procedure E1 is responsible for implementing the first step of operations D1, D2, and D3. It generates all single-edge additions of an input graph \(G\), using ApplyAdDEDGE to propagate the list of cycles. Its complexity is \(\mathcal{O}(|\mathcal{C}|n^{3})\), as it requires each pair of vertices of \(G\) to be checked, and for each non-adjacent pair ApplyAdDEDGE is used to propagate cycles. Pseudocode is shown in Algorithm 3. ```
1:procedureE1(\(G\), \(\mathcal{C}\))
2:\(S\leftarrow\phi\)
3:for\(u\in V(G)\)do
4:for\(v\in V(G)\backslash u\)do
5:if\(uv\
otin E(G)\)then
6:\(G^{\prime}\leftarrow\textsc{AddEDGE}(G,u,v)\)
7:\(\mathcal{C}^{\prime}\leftarrow\textsc{ApplyAdDEDGE}(\mathcal{C},u,v)\)
8:\(S\gets S\cup\{(G^{\prime},\mathcal{C}^{\prime},uv)\}\)
9:endif
10:endfor
11:endfor
12:return\(S\)
13:endprocedure
```  
**Algorithm 3** First edge addition procedure  
Procedure E2 is responsible for implementing the second step of operation D3. It also generates single-edge additions of an input graph, but under a certain condition. Specifically, given an input graph \(G=H+e_{1}\) with cycles \(\mathcal{C}\), as produced by E1, E2 produces all graphs \(H+\{e_{1},e_{2}\}\), where the new edge \(e_{2}\) is adjacent to \(e_{1}\). Its complexity is \(\mathcal{O}(|\mathcal{C}|n^{2})\), as ApplyAdDEDGE is used every time a new graph is generated, and each vertex is checked for eligibility. Pseudocode is shown in Algorithm 4.