# Constructing Minimally 3-Connected Graphs
## 4 Cycle Propagation Algorithm  
To check when operations D1, D2, and D3 can be performed, we must check for chording paths between specific vertices. Let \(G\) be a graph with \(n\) vertices and let \(\mathcal{C}\) denote its set of cycles. Since we will be considering only one input graph at a time, in this section \(\mathcal{C}\) is unambiguous. Given the set of cycles of the input graph \(G\), Lemmas 1 and 2 allow us to define three procedures ApplyFlipEdge, ApplyAddEdge, and ApplySubdivideEdge, which compute the set of cycles of a graph modified by flipping an edge, adding an edge, or subdividing an edge. This allows us to propagate the set of cycles for the new graphs we produce in terms of the cycles of \(G\), which in turn allows us to avoid the NP-complete problem of computing all the cycles of a graph. The procedures described in this section rely on two simpler procedures, ChordCycle and Chords, which are defined informally below. * ChordCycle(\(C,v_{1},v_{2}\)): This is the procedure described in Lemma 1. Given a cycle \(C\) and a pair of vertices \(v_{1}\) and \(v_{2}\) which both occur in the cycle, but are not adjacent, return a pair of cycles generated as follows: The first cycle is created by starting at \(v_{1}\), then proceeding to \(v_{2}\), and then following the existing cycle from \(v_{2}\) back to \(v_{1}\). The second cycle begins with \(v_{1}\) and proceeds along the existing cycle until \(v_{2}\) is reached, and then returns to \(v_{1}\). That is, if the existing cycle consists of vertices \[w_{1},w_{2},\ldots,w_{i},v_{1},w_{i+1},\ldots,w_{j},v_{2},w_{j+1},\ldots,w_{k},\] then the two new cycles will consist of vertices \[v_{2},w_{j+1},\ldots,w_{k},w_{1},\ldots,v_{1}\] and \[v_{1},w_{i+1},\ldots,w_{j},v_{2}.\] Its complexity is \(\mathcal{O}(n)\). * ChordS(\(C,v_{1},v_{2}\)): This procedure simply determines whether an edge chords a cycle. Given a cycle \(C\) and two vertices \(v_{1}\) and \(v_{2}\), determine whether there is an edge \(v_{1}v_{2}\) that chords \(C\). Its complexity is \(\mathcal{O}(n)\). Next, we present the three procedures ApplyFlipEdge, ApplyAddEdge and ApplySubdivideEdge, respectively. 1. ApplyFlipEdge(\(\mathcal{C},a,b,c\)): This procedure is also described informally, as its steps closely follow the cases in the proof of Lemma 2. Given the set \(\mathcal{C}\) of cycles of a graph \(G\) and vertices \(a\), \(b\), and \(c\) with edges \(ab\) and \(bc\), but no edge \(ac\), ApplyFlipEdge generates the list of cycles of the graph \(G^{\prime}\) produced by replacing edge \(ab\) with a new edge \(ac\), using the procedure outlined with Lemma 2. Its complexity is \(\mathcal{O}(|\mathcal{C}|^{2}n)\). 2. ApplyAddEdge(\(\mathcal{C},a,b\)): This procedure computes the resulting cycles when adding an edge to a graph, where \(\mathcal{C}\) is the set of cycles and \(a\) and \(b\) are two non-adjacent vertices. It creates the new set of cycles by adding the cycles from the old graph and the new cycles created by ChordCycle for any cycle that is chorded by \(ab\). Its complexity is \(\mathcal{O}(|\mathcal{C}|n)\). Pseudocode is shown in Algorithm 1. ```
1:procedureApplyAddEdge(\(\mathcal{C},a,b\))
2:\(S\leftarrow\phi\)
3:for\(C\in\mathcal{C}\)do
4:\(S\gets S\cup\{C\}\)
5:ifChords(\(C,a,b\))then
6:\(C_{1},C_{2}\leftarrow\textsc{ChordCycle}(C,a,b)\)
7:\(S\gets S\cup\{C_{1},C_{2}\}\)
8:endif
9:endfor
10:endprocedure
```  
**Algorithm 1** Compute cycles for an edge addition  
ApplySubdivideEdge(\(\mathcal{C},a,b,c\)): This procedure computes cycles resulting when subdividing an edge, where \(\mathcal{C}\) is the set of cycles of the graph, \(a\) and \(b\) are two adjacent vertices, and vertex \(c\) is being added to subdivide the edge \(ab\). Its complexity is \(\mathcal{O}(|\mathcal{C}|n)\). Pseudocode is shown in Algorithm 2.