# Space-Efficient Fully Dynamic DFS
## 5 Linear Space Dynamic DFS  
In this section, we propose a linear space fast dynamic DFS algorithm. In Section 4.2, we prove that there is no need to support deletion of points from \(\mathcal{G}\) even if there are some deletion updates of edges and vertices. This means we can bring a static data structure for the queries \(Q\) and \(Q^{\prime}\) rather than a dynamic one. Indeed, the data structure by [PERSON] and [PERSON] [21] can solve the ORS query in _rank space_. The rank space with \(k\) points is a \([1,k]\times[1,k]\) grid where all points differ in both \(x\)- and \(y\)-coordinates. For the rank space with \(k\) points, their data structure can solve ORS query in \(O(\log^{\varepsilon}k)\) time for an arbitrary \(0<\varepsilon<1\), can be constructed in \(O(k\sqrt{\log k})\) time, and occupies \(O(k\log k)\) bits of space. Though \(\mathcal{G}\) is not a rank space, we can convert \(\mathcal{G}\) to the rank space by using bit vectors. Please note that this kind of conversion is regularly employed for various orthogonal range search data structures (e.g., see [22]). So, in the proof below we do not show the conversion from \(\mathcal{G}\) to a rank space, but show that from the adjacency list of \(G\) to a rank space directly. Lemma 4: _There exists a data structure \(\mathcal{D}\) which can solve both ORS and ORP queries on \(\mathcal{G}\) in \(O(\log^{\varepsilon}n)\) time for each for arbitrary \(0<\varepsilon<1\). This data structure requires \(O(m\log n)\) bits of space and can be built in \(O(m\sqrt{\log n})\) time._  
Figure 2: The configuration of \(path(x,y)\) and \(w\) in \(T\) that can appear in \(Q^{\prime}(w,x,y)\) and cannot appear in \(Q(T(w),x,y)\). Proof. : Let \(d_{i}\) be the degree of a vertex \(v\) in \(G\) whose vertex id is \(i\) and \(M_{i}=\sum_{j=0}^{i-1}d_{j}\) (\(M_{0}=0\)). Now we have \(M_{n}=2m\), since \(G\) is an undirected graph. We construct a rank space \(\mathcal{R}\) satisfying the following condition: for two vertices \(v,w\) with \(f(v)=i\) and \(f(w)=j\), there exists an edge between \(v\) and \(w\) in \(G\) iff there exists a point within \([M_{i}+1,M_{i+1}]\times[M_{j}+1,M_{j+1}]\) in \(\mathcal{R}\). This can be done by the following procedure. First, prepare two arrays \(A,B\) with \(A[i]=B[i]=M_{i}\) for \(i=0,\ldots,n-1\). Then for each edge \(e=(u,v)\) in \(G\), increment \(A[f(u)],B[f(v)],A[f(v)]\) and \(B[f(u)]\) by one and then place two points on the coordinates \((A[f(u)],B[f(v)])\) and \((A[f(v)],B[f(u)])\) in \(\mathcal{R}\). When all edges are processed, \(\mathcal{R}\) satisfies the above condition. Besides \(\mathcal{R}\), we construct a bit vector with \(B=0^{d_{0}}10^{d_{1}}1\cdots 0^{d_{n-1}}1\). Here for \(i=0,\ldots,n\), \(\mathtt{rank}_{0}(\mathtt{select}_{1}(i,B),B)=M_{i}\) and \(\mathtt{rank}_{1}(\mathtt{select}_{0}(j,B),B)=i\) for \(M_{i}+1\leq j\leq M_{i+1}\) (\(i\
eq n\)). These mean that the bit vector for \(B\) enables us to interconvert between the vertex id \(f(\cdot)\) and the coordinate in \(\mathcal{R}\) in \(O(1)\) time. Therefore, given an ORS query with a rectangle \(R\) on \(\mathcal{G}\) we can solve it as follows. First, convert the coordinates of \(R\) into that in \(\mathcal{R}\) by the bit vector for \(B\). Second, solve the converted ORS query on \(\mathcal{R}\) by the data structure of [PERSON] and Puglisi [21]. Finally, if the answer is \(\emptyset\) then the original answer is also \(\emptyset\). Otherwise the answer is again converted to the vertex id by the bit vector for \(B\). The overall cost for single ORS query is thus \(O(\log^{\epsilon}n)\). Please note that the bit vector requires only \((n+2m)H_{0}(B)+o(m)\leq n\log\frac{e(n+2m)}{n}+o(m)=o(m)\log n\) bits of space. We above mentioned only the ORS query, but the data structure for the ORP query can be built in a similar way. Let \(\mathcal{R}^{\prime}\) be a rank space constructed by flipping \(\mathcal{R}\) vertically; i.e., \(\mathcal{R}^{\prime}\) is constructed by putting a point on coordinates \((i,2m+1-j)\) for every point \((i,j)\) on \(\mathcal{R}\).