Abstract
We present a novel spaceefficient graph coarsening technique for nvertex 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 socalled structuremaintaining 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 Hminorfree graphs for any fixed graph H. This allows us to construct the succinct encoding scheme for Hminorfree 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 Hminorfree 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.
BibTeX  Entry
@InProceedings{kammer_et_al:LIPIcs.ISAAC.2022.62,
author = {Kammer, Frank and Meintrup, Johannes},
title = {{SpaceEfficient Graph Coarsening with Applications to Succinct Planar Encodings}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {62:162:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772587},
ISSN = {18688969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17347},
URN = {urn:nbn:de:0030drops173478},
doi = {10.4230/LIPIcs.ISAAC.2022.62},
annote = {Keywords: planar graph, Hminorfree, spaceefficient, separator, tree decomposition}
}
Keywords: 

planar graph, Hminorfree, spaceefficient, separator, tree decomposition 
Collection: 

33rd International Symposium on Algorithms and Computation (ISAAC 2022) 
Issue Date: 

2022 
Date of publication: 

14.12.2022 