Biconnectivity, st-numbering and other applications of DFS using O(n) bits

Highlights：

• We consider space efficient implementations of some classical applications of DFS including testing biconnectivity and/or 2-edge connectivity, producing a sparse spanning biconnected subgraph of a given biconnected graph, computing chain decomposition and st-numbering, and computing topological sort and strongly connected components etc.

• Classical linear time algorithms for these problems typically use Ω(nlg⁡n) bits. We improve the space bound by providing O(n)-bit implementations for all these applications. Our algorithms take O(mlgc⁡nlg⁡lg⁡n) time for some small constant c (where c≤2).

• Central to our implementation is a succinct representation of the DFS tree and a space efficient partitioning of the DFS tree into connected subtrees, which could find possible other applications for designing other space efficient graph algorithms.