# Space-Efficient Fully Dynamic DFS
## 4 Query Reduction to Orthogonal Range Search Problem
### Original Reduction  
First we describe the original reduction of queries \(Q\) and \(Q^{\prime}\)[4] proposed by [PERSON] et al. In their paper, the ORS (ORP) query is not explicitly used, but is implicitly used. Indeed, their method to answer \(Q\) and \(Q^{\prime}\) is equivalent to solving \(O(\log n)\) ORS (ORP) queries on the adjacency matrix of \(G\); details are described below. We later use part of their ideas.  
Now we describe that how a set of points is constructed from \(G\). The high-level idea is quite simple: the vertices in \(G\) are numbered from \(0\) to \(n-1\), and an adjacency matrix according to this numbering is constructed. Let us go into detail. First, a heavy-light (HL) decomposition [19] of \(T\) is calculated. Then the order \(\mathcal{L}\) of vertices is decided according to the pre-order traversal of \(T\), such that for the first time a vertex \(v\) is visited, the next vertex to visit is one that is directly connected with a heavy edge derived from the HL decomposition. Next, the vertices of \(G\) (except \(r\)) are numbered from \(0\) to \(n-1\) according to \(\mathcal{L}\); here the vertex id of \(v\) is denoted by \(f(v)\). Finally, on a 2-dimensional grid \(\mathcal{G}\), for each edge \((i,j)\) of \(G\setminus\{r\}\), we put two points on the coordinates \((f(i),f(j))\) and \((f(j),f(i))\) in \(\mathcal{G}\). This is equivalent to considering the adjacency matrix of \(G\), and thus \(2m\) points are placed.  
The order \(\mathcal{L}\) has some good features. First, for any subtree \(T(w)\) of \(T\), the vertex ids of the vertices of \(T(w)\) occupy single consecutive interval \([t_{b},t_{e}]\) since \(\mathcal{L}\) is a pre-order traversal of \(T\). Second, for any ancestor-descendant path \(path(x,y)\) in \(T\), those of \(path(x,y)\) occupy at most \(O(\log n)\) intervals \([a_{1},b_{1}],\ldots,[a_{k},b_{k}]\). This is because \(path(x,y)\) contains at most \(O(\log n)\) light edges (i.e., non-heavy edges) thanks to the property of HL decomposition [19]. Therefore, all edges in \(G\) between \(T(w)\) and \(path(x,y)\) are within \(O(\log n)\) rectangular regions \([t_{b},t_{e}]\times[a_{i},b_{i}]\)\((i=1,\ldots,k)\) on \(\mathcal{G}\). Then if \(U=\emptyset\) (e.g., the incremental case), the answer for \(Q(T(w),x,y)\) can be obtained by searching them. More specifically, if \(f(x)\leq f(y)\) we solve ORS queries on \(\mathcal{G}\) with \(R=[t_{b},t_{e}]\times[a_{i},b_{i}]\)\((i=1,\ldots,k)\) and return the point with the smallest \(y\)-coordinate among the ORS queries' answers. Otherwise, we solve ORP queries with the same rectangles and return the point with the largest \(y\)-coordinate among the ORP queries' answers. If all ORS (ORP) queries return \(\emptyset\), the answer for \(Q(T(w),x,y)\) is also \(\emptyset\). The same argument can be applied for \(Q^{\prime}(w,x,y)\) except that the rectangular regions are \([f(w),f(w)]\times[a_{i},b_{i}]\)\((i=1,\ldots,k)\).  
If \(U\
eq\emptyset\) (e.g., the fully dynamic case), deletion of points on \(\mathcal{G}\) should be supported, since the edges in \(U\) and the incident edges of the vertices in \(U\) must be removed from \(\mathcal{G}\) to prevent \(Q\) and \(Q^{\prime}\) from reporting already deleted edges. To achieve this, [PERSON] et al. (2019) uses a kind of range tree data structures to solve \(Q\) and \(Q^{\prime}\), which supports deleting a point.