# Space-Efficient Fully Dynamic DFS
## 8 Applications
### Dynamic Biconnectivity/2-Edge-Connectivity  
For the dynamic biconnectivity (2-edge-connectivity) problems, we first formally define the problem. A set \(S\) of vertices in an undirected graph \(G\) is called a _biconnected component_ iff it is the maximal set such that the removal of any one vertex in \(S\) keeps \(S\) connected. Similarly, a set \(S\) of vertices is said to be a _2-edge-connected component_ iff it is the maximal set such that the removal of any one edge whose endpoints are both in \(S\) keeps \(S\) connected. The biconnectivity (2-edge-connectivity) query takes two vertices as an input and asks whether these two vertices are in the same biconnected (2-edge-connected) component or not. The goal of the dynamic biconnectivity (2-edge-connectivity) problem is to design an algorithm which can process any on-line sequence of graph updates and biconnectivity (2-edge-connectivity) queries. The concepts related to biconnectivity and 2-edge-connectivity are articulation points and bridges. A vertex \(v\) (an edge \(e\)) in \(G\) is called an _articulation point_ (a _bridge_) iff the removal of \(v\) (\(e\)) increases the number of connected components in \(G\). Then we can say that for any DFS tree \(T\) of \(G\), two vertices \(u\) and \(v\) are in the same biconnected component iff the path from \(u\) to \(v\) in \(T\) (excluding \(u\) and \(v\) themselves) includes no articulation points. Similarly, two vertices \(u\) and \(v\) are in the same 2-edge-connected component iff the path from \(u\) to \(v\) in \(T\) contains no bridges. Therefore, now we can reduce the dynamic biconnectivity (2-edge-connectivity) problem to the following problem: to design an algorithm which can enumerate, for any on-line sequence of updates on \(G\), all articulation points and bridges after each update. In static setting, the articulation points and bridges can be listed also by DFS. Given a connected undirected graph \(G\) and its DFS tree \(T\), we first number the vertices from \(0\) to \(n-1\) by the pre-order traversal of \(T\); the id of a vertex \(v\) is denoted by \(g(v)\). Then the _high number_\(h(v)\) of a vertex \(v\) is defined by \(\min\{g(w)\mid\text{there is at least one edge in $G$ between $w$ and $T(v)$}\}\). It can be said that a vertex \(v\) is an articulation point iff \(v\) is a root of \(T\) and has multiple children, or \(v\) is a non-root vertex of \(T\) and has at least one child \(w\) with \(g(v)=h(w)\). We can also say that a tree edge \(e=(v,w)\) (\(v\) is a parent of \(w\)) is a bridge iff \(h(w)=g(v)\), and \(h(x)=g(w)\) for all children \(x\) of \(w\). Therefore, if we can calculate \(h(\cdot)\) for all vertices, we can detect all articulation points and bridges in \(O(n)\) time by simply traversing \(T\). Now the problem we want to solve is to design an algorithm such that given an undirected graph \(G\), it can compute a new DFS tree and \(h(\cdot)\) for the graph obtained by applying any \(k(\leq n)\) graph updates to \(G\). [PERSON] et al. [6] proposed an efficient method for solving this by modifying the faulttolerant DFS algorithm. Before explaining this, let us recall the fault tolerant DFS algorithm. We state in Section 3.1 that during the construction of a new DFS tree \(T^{*}\), when a path or a subtree \(x\in\mathcal{P}\cup\mathcal{T}\) (derived from DTP) is visited, an ancestor-descendant path \(p^{*}\) is extracted from \(x\) and the remaining part \(x\setminus p^{*}\) is pushed back to \(\mathcal{P}\) if originally \(x\in\mathcal{P}\) or \(\mathcal{T}\) otherwise. Let \(P_{t}\) (\(P_{p}\)) be a set of these extracted paths from \(\mathcal{T}\) (\(\mathcal{P}\)). The algorithm in Section 3.1 ensures us that \(|P_{p}|\leq k\log n\). For an extracted path \(p^{*}\in P_{t}\cup P_{p}\), let \(u(p^{*})\) and \(l(p^{*})\) be the endpoints of \(p^{*}\), where \(u(p^{*})\) is an ancestor of \(l(p^{*})\) in the new DFS tree \(T^{*}\). We describe their method to calculate \(h(\cdot)\). They use the query \(Q^{\prime}\) defined in Definition 2.