# Space-Efficient Fully Dynamic DFS
## 8 Applications
### Dynamic Biconnectivity/2-Edge-Connectivity
First, compute the initial DTP in the same way as fault tolerant DFS, and for each vertex \(v\) in some subtree \(\tau\in\mathcal{T}\), calculate the highest ancestor \(z_{v}\) among vertices \(z\in\tau\) such that there is an edge \((v,z)\) in the updated graph. This is calculated by an ORS query on \(\mathcal{G}\) with \(R=[f(v),f(v)]\times[t_{b},t_{e}]\) where \([t_{b},t_{e}]\) is the interval the vertices of \(\tau\) occupy in the (old) vertex numbering \(f(\cdot)\). Second, obtain a new DFS tree \(T^{*}\) by fault tolerant DFS tree algorithm. In constructing \(T^{*}\), simultaneously number the vertices to get the (new) vertex numbering \(g(\cdot)\). Third, for each vertex \(v\) except \(r\), attach an integer \(H(v)\) which is initialized to some constant larger than any vertex numbering \(g(\cdot)\), e.g., the number of vertices. Fourth, for each inserted edge \((v,w)\), update \(H(v)\) by \(g(w)\) and \(H(w)\) by \(g(u)\). Here for a vertex \(v\) and an integer \(k\), \"update \(H(v)\) by \(k\)\" means substituting \(\min\{H(v),k\}\) for \(H(v)\). Finally, these operations are performed. 1. For each vertex \(v\) and each path \(p^{*}\in P_{p}\), solve \(Q^{\prime}(v,u(p^{*}),l(p^{*}))\) to get an edge \((v,w)\) and update \(H(v)\) by \(g(w)\). 2. For each vertex \(v\) and each path \(p^{*}\in P_{p}\), solve \(Q^{\prime}(v,l(p^{*}),u(p^{*}))\) to get \((v,w)\) and update \(H(w)\) by \(g(v)\). 3. For each vertex \(v\) that is in some subtree \(\tau\in\mathcal{T}\) initially (i.e., when the initial DTP is calculated), let \(p^{*}_{v}\in P_{t}\) be the path which contains \(v\). Then solve \(Q^{\prime}(v,u(p^{*}_{v}),l(p^{*}_{v}))\) to get \((v,w)\) and update \(H(v)\) by \(g(w)\). 4. For each vertex \(v\) that is in some subtree \(\tau\in\mathcal{T}\) initially, let \(p^{*}_{z}\in P_{t}\) be the path which contains \(z_{v}\). Then solve \(Q^{\prime}(v,u(p^{*}_{z}),l(p^{*}_{z}))\) to get \((v,w)\) and update \(H(v)\) by \(g(w)\). [PERSON] et al. [6] show that after performing them, \(h(\cdot)\) is calculated by \(h(v)=\min\{H(w)\mid w\) is \(v\) itself or a descendant of \(v\}\). Thus, after calculating \(H(\cdot)\), \(h(\cdot)\) can be computed in \(O(n)\) time by simply traversing the new DFS tree \(T^{*}\). We bring their method to our situation. First we consider the time complexity. Except for the operations 1. to 4., we throw \(O(n)\) ORS queries, perform fault tolerant DFS and scan all inserted edges. The most time-consuming part among them is fault tolerant DFS, and takes \(O(f\cdot nk\log n)\) time with \(O(f)\) ORS (ORP) query time (Lemmas 1 and 3). The operations 3. and 4. solves \(Q^{\prime}\) for \(n\) times, thus they take \(O(f\cdot n\log n)\) time which is absorbed. However, the operations 1. and 2. solves \(Q^{\prime}\) for \(O(nk\log n)\) times since \(|P_{t}|=O(k\log n)\), and therefore they seem to take \(O(f\cdot nk\log^{2}n)\) time, which is larger than performing fault tolerant DFS. This is because \(Q^{\prime}\) is solved \(O(\log n)\) times slower than \(Q\) is. Here we show the following lemma, which implies that they take only \(O(f\cdot nk\log n)\) time. Lemma 10: _The operations 1. and 2. can be performed by solving \(O(nk\log n)\) ORS (ORP) queries in total._  
Proof. : In solving \(Q^{\prime}\), we solve ORS (ORP) queries with \(R=[f(w),f(w)]\times[a_{i},b_{i}]\) (\(i=1,\ldots,k\)), where \([a_{1},b_{1}],\ldots,[a_{k},b_{k}]\) is the intervals \(path(x,y)\) occupies in the (old) vertex numbering \(f(\cdot)\). For \(p^{*}\in P_{t}\cup P_{p}\), let \(k(p^{*})\) be the number of intervals of vertex ids \(p^{*}\) is divided into. Then it suffices to show that \(\sum_{p^{*}\in P_{t}\cup P_{p}}k(p^{*})=O(k\log n)\), since it can be said that for each vertex \(v\), \(Q^{\prime}(v,u(p^{*}),l(p^{*}))\) and \(Q^{\prime}(v,l(p^{*}),u(p^{*}))\) are solved for all \(p^{*}\in P_{t}\cup P_{p}\) by \(\sum_{p^{*}\in P_{t}\cup P_{p}}k(p^{*})\) ORS (ORP) queries.