# Direct Superbubble Detection
## Theory
### Oriented Trees and DFS-trees
Depth-first search (DFS) traverses a digraph \(G\) in the following manner: (i) pick a root \(r\in V(G)\); (ii) recursively, at \(v\in V(G)\), proceed to the \(\triangleleft\) smallest, previously-unvisited out-neighbor of \(v\); (iii) if \(v\) has no more unvisited out-neighbors, return to is \"parent\", i.e., the vertex \(par(v)\) from which \(v\) was initially reached [8]. Clearly, DFS generates a rooted tree \(T\) with directed edges \((par(v),v)\), which are known as the DFS-tree. Lemma 1: _Let \(T\) be the ordered subtree generated by DFS on a digraph \(G\), and let \((u,v)\in E(G)\) with \(u\in V(T)\). Then, \(v\in V(T)\) and either \(v\prec u\) (including \((u,v)\in E(T)\)), \(u\prec v\), or \(v\triangleleft u\). In particular, \(T\) is a search tree on \(G\)._  
Proof: Consider a DFS reaching \(u\). The search steps up to \(par(u)\) only after exhausting all out-neighbors of \(u\); hence, any edge \((u,v)\) either has been visited before by the DFS process or, otherwise, it is included as an edge as DFS steps down to the subtree of \(u\) rooted in \(v\). If \(v\) has been accessed before, then \(v\) is either an ancestor or descendant of \(u\) or \(u\) and \(v\) are incomparable w.r.t. \(\prec\). In the latter case, there are distinct children \(x\) and \(y\) of \(\operatorname{lca}(u,v)\) such that \(u\in T(x)\) and \(v\in T(y)\). In a DFS, \(T(y)\) is traversed before \(T(x)\) if \(y\) comes before \(x\) in the out-neighbor order of \(\operatorname{lca}(u,v)\), and thus, \(v\triangleleft u\). By the construction of DFS, \(x\in V(T)\) is reachable from the root \(r\) along a path in \(G\); hence, \(V(T)\subseteq V[r]\). Suppose there is \(x\in V[r]\setminus V(T)\). Along a path \(p\) from \(r\) to \(x\), let \(x^{\prime}\) be the first vertex not reachable from \(V(T)\), i.e., there is an edge \((u,x^{\prime})\in E(G)\) with \(u\in V(T)\) and \(x^{\prime}\
otin V(T)\), contradicting the first assertion of the lemma. The DFS process proceeds on \(V[r]\) in such a way that the preorder \(\rho\) of the DFS-tree \(T\) rooted at \(r\) records the order in which the vertices are discovered, while the postorder \(\pi\) describes the order in which vertices are completed, i.e., \"left\", by ascending back to their parent. To see this, denote by \(\rho^{\prime}\) and \(\pi^{\prime}\) the order in which vertices are discovered and completed by DFS started at \(r\). By construction, DFS accesses the out-neighbors of \(v\) in \(\triangleleft\) order of the children of \(v\) and completes the traversal of a subtree rooted at a child \(v^{\prime}\) of \(v\) before proceeding to the subtree of another child. Thus, if \(u\) and \(v\) are incomparable w.r.t. \(\prec\) in \(T\), then \(\rho^{\prime}(u)<\rho^{\prime}(v)\) and \(\pi^{\prime}(u)<\pi^{\prime}(v)\) if and only if \(u\triangleleft v\) in the sibling order. It also follows directly from the definition of DFS that we have \(\rho^{\prime}(u)<\rho^{\prime}(v)\) if \(v\prec u\) and \(\pi^{\prime}(u)<\pi^{\prime}(v)\) if \(u\prec v\). Hence, \(\rho^{\prime}\) and \(\pi^{\prime}\) indeed coincide with the preorder \(\rho\) and the postorder \(\pi\) for the traversal of DFS tree \(T\). DFS on a graph \(G\) is therefore completely described by the oriented DFS tree \(T\), i.e., the sibling and ancestor order on \(V[r]\), and coincides with DFS on \(T\) itself. Hence, the condition that \(v\) has been accessed before \(u\) can expressed simply as \(\rho(v)<\rho(u)\). If \(u\) and \(v\) are comparable on \(T\), their relative order is determined by Equation (2). We therefore obtain the following simple characterization of DFS-trees:  
Corollary 1: _A search tree \(T\) with postorder \(\rho\) on \(G\) is a DFS-tree if and only if an edge \((u,v)\in E(G[V(T)])\) is either (i) a tree edge, (ii) an edge connecting two non-adjacent comparable vertices in \(T\), or (iii) \(\rho(v)<\rho(u)\) whenever \(u\) and \(v\) are incomparable w.r.t. \(\prec\) in \(T\)._  
As a consequence, we have the following classification of edges w.r.t. a DFS-tree.