KIT | KIT-Bibliothek | Impressum | Datenschutz

Synchronized planarity with applications to constrained planarity problems

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


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⁸).

Verlagsausgabe §
DOI: 10.5445/IR/1000138390
Veröffentlicht am 01.10.2021
DOI: 10.4230/LIPIcs.ESA.2021.19
Zitationen: 9
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2021
Sprache Englisch
Identifikator ISBN: 978-3-9597720-4-4
ISSN: 1868-8969
KITopen-ID: 1000138390
Erschienen in 29th Annual European Symposium on Algorithms (ESA 2021): 6-8 September 2021, online. Ed.: P. Mutzel
Veranstaltung 29th Annual European Symposium on Algorithms (ESA 2021), Online, 06.09.2021 – 08.09.2021
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Seiten Art.-Nr.: 19
Serie Leibniz International Proceedings in Informatics (LIPIcs) ; 204
Nachgewiesen in Scopus
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page