  We consider the problem of compactly representing the Depth First Search
(DFS) tree of a given undirected or directed graph having $n$ vertices and $m$
edges while supporting various DFS related queries efficiently in the RAM with
logarithmic word size. We study this problem in two well-known models: {\it
indexing} and {\it encoding} models. While most of these queries can be
supported easily in constant time using $O(n \lg n)$ bits\footnote{We use $\lg$
to denote logarithm to the base $2$.} of extra space, our goal here is, more
specifically, to beat this trivial $O(n \lg n)$ bit space bound, yet not
compromise too much on the running time of these queries. In the {\it indexing}
model, the space bound of our solution involves the quantity $m$, hence, we
obtain different bounds for sparse and dense graphs respectively. In the {\it
encoding} model, we first give a space lower bound, followed by an almost
optimal data structure with extremely fast query time. Central to our algorithm
is a partitioning of the DFS tree into connected subtrees, and a compact way to
store these connections. Finally, we also apply these techniques to compactly
index the shortest path structure, biconnectivity structures among others.
