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.ESA.2021.19
URN: urn:nbn:de:0030-drops-146009
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14600/
Go to the corresponding LIPIcs Volume Portal

Bläsius, Thomas ; Fink, Simon D. ; Rutter, Ignaz

Synchronized Planarity with Applications to Constrained Planarity Problems

pdf-format:
LIPIcs-ESA-2021-19.pdf (0.9 MB)

Abstract

We introduce the problem Synchronized Planarity. Roughly speaking, its input is a loop-free multi-graph together with synchronization constraints that, e.g., match pairs of vertices of equal degree by providing a bijection between their edges. Synchronized Planarity then asks whether the graph admits a crossing-free embedding into the plane such that the orders of edges around synchronized vertices are consistent. We show, on the one hand, that Synchronized Planarity can be solved in quadratic time, and, on the other hand, that it serves as a powerful modeling language that lets us easily formulate several constrained planarity problems as instances of Synchronized Planarity. In particular, this lets us solve Clustered Planarity in quadratic time, where the most efficient previously known algorithm has an upper bound of O(n⁸).

BibTeX - Entry

@InProceedings{blasius_et_al:LIPIcs.ESA.2021.19,
  author =	{Bl\"{a}sius, Thomas and Fink, Simon D. and Rutter, Ignaz},
  title =	{{Synchronized Planarity with Applications to Constrained Planarity Problems}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14600},
  URN =		{urn:nbn:de:0030-drops-146009},
  doi =		{10.4230/LIPIcs.ESA.2021.19},
  annote =	{Keywords: Planarity Testing, Constrained Planarity, Cluster Planarity, Atomic Embeddability}
}

Keywords: Planarity Testing, Constrained Planarity, Cluster Planarity, Atomic Embeddability
Collection: 29th Annual European Symposium on Algorithms (ESA 2021)
Issue Date: 2021
Date of publication: 31.08.2021

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