  Depth First Search (DFS) tree is a fundamental data structure for solving
graph problems. The DFS tree of a graph $G$ with $n$ vertices and $m$ edges can
be built in $O(m+n)$ time. Till date, only a few algorithms have been designed
for maintaining incremental DFS. For undirected graphs, the two algorithms,
namely, ADFS1 and ADFS2 [ICALP14] achieve total $O(n^{3/2}\sqrt{m})$ and
$O(n^2)$ time respectively. For DAGs, the only non-trivial algorithm, namely,
FDFS [IPL97] requires total $O(mn)$ time.
  In this paper, we carry out extensive experimental and theoretical evaluation
of existing incremental DFS algorithms in random and real graphs, and derive
the following results.
  1- For insertion of uniformly random sequence of $n \choose 2$ edges, ADFS1,
ADFS2 and FDFS perform equally well and are found to take $\Theta(n^2)$ time
experimentally. This is quite surprising because the worst case bounds of ADFS1
and FDFS are greater than $\Theta(n^2)$ by a factor of $\sqrt{m/n}$ and $m/n$
respectively. We complement this result by probabilistic analysis of these
algorithms proving $\tilde{O}(n^2)$ bound on the update time. Here, we derive
results about the structure of a DFS tree in random graphs, which are of
independent interest.
  2- These insights led us to design an extremely simple incremental DFS
algorithm for both undirected and directed graphs. This algorithm theoretically
matches and experimentally outperforms the state-of-the-art in dense random
graphs. It can also be used as a single-pass semi-streaming algorithm for
incremental DFS and strong connectivity in random graphs.
  3- Even for real graphs, both ADFS1 and FDFS perform much better than their
theoretical bounds. Here again, we present two simple algorithms for
incremental DFS for directed and undirected real graphs. In fact, our algorithm
for directed graphs almost always matches the performance of FDFS.
