Depth first search (DFS) tree is a fundamental data structure for solving various problems in graphs. It is well known that it takes $O(m+n)$ time to build a DFS tree for a given undirected graph $G=(V,E)$ on $n$ vertices and $m$ edges. We address the problem of maintaining a DFS tree when the graph is undergoing updates (insertion and deletion of vertices or edges). We present the following results for this problem: (1) Fault tolerant DFS tree: There exists a data structure of size $\tilde{O}(m)$ (where $\tilde{O}()$ hides the polylogarithmic factors) which can be preprocessed in $\tilde{O}(m)$ time such that given any set ${\cal F}$ of failed vertices or edges, a DFS tree of the graph $G\setminus {\cal F}$ can be reported in $\tilde{O}(n|{\cal F}|)$ time. (2) Fully dynamic DFS tree: There exists a fully dynamic algorithm for maintaining a DFS tree that takes $\tilde{O}(m)$ time for preprocessing and worst case $\tilde{O}(\sqrt{mn})$ time per update for any arbitrary online sequence of updates. (3) Incremental DFS tree: There exists an incremental algorithm for maintaining a DFS tree that takes $\tilde{O}(m)$ time for preprocessing and worst case $\tilde{O}(n)$ time per update for any arbitrary online sequence of edge insertion. These are the first $o(m)$ worst case time results for maintaining a DFS tree of a dense graph in a dynamic environment. Moreover, our fully dynamic algorithm provides, in a seamless manner, the first deterministic algorithm for dense graphs with $O(1)$ query time and $o(m)$ worst case update time for connectivity, biconnectivity, and 2-edge connectivity in the dynamic subgraph model.

Given an undirected graph G = (V, E) on n vertices and m edges, we address the problem of maintaining a DFS tree when the graph is undergoing updates (insertion and deletion of vertices or edges). We present the following results for this problem. 1. Fault tolerant DFS tree: There exists a data structure of size Õ(m)1 such that given any set ℱ of failed vertices or edges, a DFS tree of the graph G\ℱ can be reported in Õ(n|ℱ|) time. 2. Fully dynamic DFS tree: There exists a fully dynamic algorithm for maintaining a DFS tree that takes worst case time per update for any arbitrary online sequence of updates. 3. Incremental DFS tree: Given any arbitrary online sequence of edge insertions, we can maintain a DFS tree in Õ(n) worst case time per edge insertion. These are the first o(m) worst case time results for maintaining a DFS tree in a dynamic environment. Moreover, our fully dynamic algorithm provides, in a seamless manner, the first deterministic algorithm with O(1) query time and o(m) worst case update time for the dynamic subgraph connectivity, biconnectivity, and 2-edge connectivity.