# Space-Efficient Fully Dynamic DFS
## 8 Applications
### Dynamic Biconnectivity/2-Edge-Connectivity
Let us recall that the union of all paths in \(P_{p}\) equals to the union of paths in \(\mathcal{P}\), a set of ancestor-descendant paths of the initial DTP. Let \(S\) be the vertices of the union of all paths in \(P_{p}\). Since \(|\mathcal{P}|\leq k\) (see Definition 1), \(S\) occupies at most \(N_{I}=O(k\log n)\) intervals. Thus, even if \(S\) is divided into \(|P_{p}|=O(k\log n)\) paths, the number of intervals to consider is at most \(N_{I}+|P_{p}|=O(k\log n)\). Hence \(\sum_{p^{*}\in P_{t}\cup P_{p}}k(p^{*})=O(k\log n)\). In this way we can say the time complexity is \(O(f\cdot nk\log n)\). Next we consider the required space, but it is easy. The key point is again that the whole adjacency list of \(G\) is not needed due to the usage of the query \(Q^{\prime}\). In these processes, we must store the endpoints of each path in \(P_{t}\cup P_{p}\). For each vertex \(v\), we must retain \(g(v)\), \(H(v)\), \(h(v)\), \(z_{v}\), and a pointer to a path in \(P_{t}\cup P_{p}\)\(v\) is contained, and so on. However, these sum up to only \(O(n)\) words of information, thus these takes only \(O(n\log n)=o(m)\log n\) bits. Therefore, we prove the following. **Lemma 11**. : _Given an undirected graph \(G\) and its DFS tree \(T\), there exists an algorithm such that with \(O(m\sqrt{\log n})\) preprocessing time, articulation points and bridges of the graph obtained by applying any \(k(\leq n)\) updates (vertex/edge insertions/deletions) to \(G\) can be all enumerated in \(O(nk\log^{1+\epsilon}n)\) (\(O(nk\log^{2}n)\)) time. This algorithm requires \(O(m\log n)\) (\((m+o(m))\log n+O(nk\log^{2}n)\)) bits of space once the preprocessing is finished._  
We propose an efficient fully dynamic biconnectivity/2-edge-connectivity algorithm including vertex updates using Lemma 11. For 2-edge-connectivity, it can be observed from the definition that each vertex belongs to exactly one 2-edge-connected component. With the relation between 2-edge-connectivity and bridges, we can number the 2-edge-connected components of \(G\), and attach to each vertex \(v\) the id of the 2-edge-connected component \(v\) belongs to, by simply traversing \(T^{*}\). Then the 2-edge-connectivity query can be answered in the same way as the connectivity query. For biconnectivity, we first build an LCA data structure [20] for \(T^{*}\) after each update. We also compute, for each vertex \(v\), the lowest ancestor \(a(v)\) among articulation points (excluding \(v\) itself). They can be all computed in \(O(n)\) time by simply traversing \(T^{*}\) after each update. Then for the biconnectivity query with two input vertices \(v,w\), first get \(x=LCA(v,w)\) in \(T^{*}\) by querying the LCA data structure. Now the path from \(v\) to \(w\) in \(T^{*}\) is indeed two ancestor-descendant paths from \(v\) to \(x\) and from \(x\) to \(w\) in \(T^{*}\). We can check whether these paths contain articulation vertices or not by comparing \(g(a(v))\) to \(g(x)\) and \(g(a(w))\) to \(g(x)\). For example, if \(g(x)\leq g(a(v))\), the path from \(v\) to \(x\) in \(T^{*}\) contains at least one articulation points; otherwise does not. For one biconnectivity query the overall time is \(O(1)\) including the LCA query. The additional space required is also \(O(n\log n)=o(m)\log n\) bits because the LCA data structure takes only \(O(n\log n)\) bits. Therefore, we obtain the following theorem. **Theorem 7**. : _Given an undirected graph \(G\), there exists an algorithm such that with \(O(m\sqrt{\log n})\) preprocessing time, for any on-line sequence of graph updates (edge/vertex insertion/deletion), biconnectivity queries and 2-edge-connectivity queries, each update can be processed in worst-case \(O(\sqrt{mn}\log^{0.75+\epsilon}n)\) time (\(O(\sqrt{mn}\log^{1.25}n)\) time) and each query can be answered in worst-case \(O(1)\) time. This algorithm requires \(O(m\log n)\) bits (\((3m+o(m))\log n\) bits) once the preprocessing is finished._  
**Author Contributions:** conceptualization, K.N. ; methodology, K.N. and K.S. ; software, K.N. ; validation, K.N. and K.S. ; formal analysis, K.N.