Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings

Michael Elberfeld, Frank Kammer, Johannes Meintrup

We call a graph $G$ separable if a balanced separator can be computed for $G$ of size $O(n^c)$ with $c<1$. Many real-world graphs are separable such as graphs of bounded genus, gra…