2026-07-25T01:58:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17347 2024-03-06T10:59:31Z ddc:004 open_access

Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings Kammer, Frank Meintrup, Johannes planar graph H-minor-free space-efficient separator tree decomposition We present a novel space-efficient graph coarsening technique for n-vertex planar graphs G, called cloud partition, which partitions the vertices V(G) into disjoint sets C of size O(log n) such that each C induces a connected subgraph of G. Using this partition 𝒫 we construct a so-called structure-maintaining minor F of G via specific contractions within the disjoint sets such that F has O(n/log n) vertices. The combination of (F, 𝒫) is referred to as a cloud decomposition. For planar graphs we show that a cloud decomposition can be constructed in O(n) time and using O(n) bits. Given a cloud decomposition (F, 𝒫) constructed for a planar graph G we are able to find a balanced separator of G in O(n/log n) time. Contrary to related publications, we do not make use of an embedding of the planar input graph. We generalize our cloud decomposition from planar graphs to H-minor-free graphs for any fixed graph H. This allows us to construct the succinct encoding scheme for H-minor-free graphs due to Blelloch and Farzan (CPM 2010) in O(n) time and O(n) bits improving both runtime and space by a factor of Θ(log n). As an additional application of our cloud decomposition we show that, for H-minor-free graphs, a tree decomposition of width O(n^{1/2 + ε}) for any ε > 0 can be constructed in O(n) bits and a time linear in the size of the tree decomposition. A similar result by Izumi and Otachi (ICALP 2020) constructs a tree decomposition of width O(k √n log n) for graphs of treewidth k ≤ √n in sublinear space and polynomial time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Frank Kammer and Johannes Meintrup 2022 Is Part Of LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2022.62 urn:nbn:de:0030-drops-173478 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.62 eng https://creativecommons.org/licenses/by/4.0/legalcode