License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.62
URN: urn:nbn:de:0030-drops-173478
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17347/
Go to the corresponding LIPIcs Volume Portal

Kammer, Frank ; Meintrup, Johannes

Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings

pdf-format:
LIPIcs-ISAAC-2022-62.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{kammer_et_al:LIPIcs.ISAAC.2022.62,
  author =	{Kammer, Frank and Meintrup, Johannes},
  title =	{{Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{62:1--62:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17347},
  URN =		{urn:nbn:de:0030-drops-173478},
  doi =		{10.4230/LIPIcs.ISAAC.2022.62},
  annote =	{Keywords: planar graph, H-minor-free, space-efficient, separator, tree decomposition}
}

Keywords: planar graph, H-minor-free, space-efficient, separator, tree decomposition
Collection: 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Issue Date: 2022
Date of publication: 14.12.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI