# Space-Efficient Fully Dynamic DFS
## 7 More Space-Efficient Dynamic DFS
### Amortized Update Time Dynamic DFS
To do this, we also retain during phase \(j\) an integer sequence \(M_{j}[0...n_{j}]\), where \(M_{j}[i]\) is the number of points in the upper (or lower) triangular part of \(\mathcal{G}_{j}\) whose \(x\)-coordinate is less than \(i\). Then \(0=M_{j}[0]\leq M_{j}[1]\leq\cdots\leq M_{j}[n_{j}]=m_{j}\) holds. The \(y\)-coordinates of the points whose \(x\)-coordinate is \(i\) are stored in \(S_{j}[M_{j}[i]+1...M_{j}[i+1]]\); we call this subsequence a _block_\(i\) of \(S_{j}\). We impose a condition on \(S_{j}\) that each block of \(S_{j}\) is sorted in ascending order. Please note that \(S_{j}\) takes \(m_{j}\log n_{j}\) bits and \(M_{j}\) takes \(O(n_{j}\log m_{j})=o(m_{j})\log n_{j}\) bits. Now we describe the way to rebuild the data structures space-efficiently at the end of phase \(j\). First, destroy \(B_{j}\) and \(\mathcal{W}_{j}\). Second, sort the information of last \(c_{j}\) updates, i.e., the inserted or deleted edges during the last \(c\) updates, in the same order as \(S_{j}\). This can be performed as follows. First convert this information to tuples \((x_{i},y_{i},d_{i})\) where \((x_{i},y_{i})\) is the vertex ids (according to \(\mathcal{L}_{j}\)) of the endpoints of the edge with \(x_{i}>y_{i}\) (or \(x_{i}<y_{i}\) in the lower triangular case), and \(d_{i}\) is information of 1 bit which represents whether the edge is inserted or deleted (here if there are inserted vertices, they are numbered from \(n_{j}\)). Second sort them by the ascending order of \(x_{i}\). If there are some tuples which share \(x_{i}\), they are sorted by the ascending order of \(y_{i}\). Please note that since the number of edges inserted or deleted during \(c_{j}\) updates is up to \(o(m_{j})\), sorting can be performed in linear time (i.e., \(o(m_{j})\) time) and \(o(m_{j})\log n_{j}\) bits of working space by radix sort. Third, create a new array \(S^{\prime}_{j+1}[1...m_{j+1}]\) and \(M^{\prime}_{j+1}[0...n_{j+1}]\), which retains information of all edges in \(G_{j+1}\) with the vertex numbering from \(\mathcal{L}_{j}\)This can be done by simply scanning the tuples and \(S_{j}\) simultaneously and merging them, since they are sorted in the same order. Fourth, destroy \(S_{j}\) and \(M_{j}\), and decide the order \(\mathcal{L}_{j+1}\) of vertices in \(G_{i+1}\) according to the pre-order traversal of \(T_{j+1}\). Fifth, create \(S_{j+1}[1...m_{j+1}]\) and \(M_{j+1}[0...n_{j+1}]\) from \(S_{j+1}^{\prime}\) and \(M_{j+1}^{\prime}\), and destroy \(S_{j+1}^{\prime}\) and \(M_{j+1}^{\prime}\). The detail of this process is described later. Finally, build \(\mathcal{W}_{j+1}\) and \(B_{j+1}\) from \(M_{j+1}\) and \(S_{j+1}\). Then we are ready for phase \((j+1)\). The remaining part is creating \(S_{j+1}\) and \(M_{j+1}\) from \(S_{j+1}^{\prime}\) and \(M_{j+1}^{\prime}\). For simplicity, let \(t=j+1\), and suppose that we now focus on the upper triangular part of \(\mathcal{G}_{t}\) as in Section 6.2 (even if we focus on the lower triangular part of \(\mathcal{G}_{t}\) as in Section 6.3, we can perform this in almost the same way). First, construct an old-to-new correspondence table \(N\) of vertex numbering: \(N[i]\) is the vertex id from \(\mathcal{L}_{t}\) of a vertex whose vertex id from \(\mathcal{L}_{j}\) is \(i\). Then the pseudocode for converting \(S_{t}^{\prime}\) and \(M_{t}^{\prime}\) to \(S_{t}\) and \(M_{t}\) is given in Algorithm 3. Here \(\operatorname{inc}(\cdot)\) and \(\operatorname{dec}(\cdot)\) stand for the increment and decrement (resp.) of this variable by one. This seems to be a bit complicated, but is equivalent to performing a kind of counting sort for two times. In the first part (lines 1-12 of Algorithm 3), we convert the old vertex id to the new one, let the points (i.e., edges in \(G_{t}\)) in the \"lower\" triangular part of \(\mathcal{G}_{t}\), and sort them by their \(x\)-coordinates. In the second part (lines 14-21), we sort them by their \(y\)-coordinates and record their \(x\)-coordinates (see line 19) in \(S_{t}\).