2026-07-21T23:34:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24937 2026-02-09T08:02:18Z ddc:004 open_access

Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings Elberfeld, Michael Kammer, Frank Meintrup, Johannes Depth-First Search Succinct Space Efficient Separable Graphs Planar Graphs Table Lookup r-Division We call a graph G separable if a balanced separator can be computed for G of size O(n^ε) with ε < 1. Many real-world graphs are separable such as graphs of bounded genus, graphs of constant treewidth, and graphs excluding a fixed minor. In particular, the well-known planar graphs are separable. We present a succinct encoding of separable graphs G such that, after the encoding is computed, any number of depth-first searches (DFS) can be performed from any given start vertex, each in o(n) time and o(n) bits in the word RAM model. After the execution of a DFS, the succinct encoding of G is augmented such that the DFS tree is encoded inside the encoding while maintaining succinctness. Afterward, the encoding provides common DFS-related queries in constant time. These queries include queries such as lowest-common ancestor of two given vertices in the DFS tree or queries that output the lowpoint of a given vertex in the DFS tree. Furthermore, for planar graphs, we show that the succinct encoding can be computed in O(n) bits and expected linear time, and a compact variant can be constructed in O(n) time and bits. For other separable graph classes 𝒢 the runtime and space usage depends on the specific algorithms used to find balanced separators in graphs of 𝒢. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Elberfeld and Frank Kammer and Johannes Meintrup 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.29 urn:nbn:de:0030-drops-249379 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.29 eng https://creativecommons.org/licenses/by/4.0/legalcode