Synchronized Planarity with Applications to Constrained Planarity Problems
ACM Transactions on Algorithms · 31.10.2023 · 19 (4) · 1-23
DOI: 10.1145/3607474 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 26.09.2023. Verfasst von Thomas Bläsius und 2 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 41 Literaturangaben. Gefördert von: Deutsche Forschungsgemeinschaft.
Abstract (Originalsprache)
We introduce the problem S ynchronized P lanarity . 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. S ynchronized P lanarity 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 S ynchronized P lanarity 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 S ynchronized P lanarity . In particular, this lets us solve C lustered P lanarity in quadratic time, where the most efficient previously known algorithm has an upper bound of O ( n 8 ).
Förderung
- Deutsche Forschungsgemeinschaft
Zitieren
APA
Bläsius, T., Fink, S. D., & Rutter, I. (2023). Synchronized Planarity with Applications to Constrained Planarity Problems. ACM Transactions on Algorithms, 19(4), 1-23. https://doi.org/10.1145/3607474
Vancouver
Bläsius T, Fink SD, Rutter I. Synchronized Planarity with Applications to Constrained Planarity Problems. ACM Transactions on Algorithms. 2023;19(4):1-23. doi:10.1145/3607474
BibTeX
@article{Blsius2023,
author = {Bläsius, Thomas and Fink, Simon D. and Rutter, Ignaz},
title = {Synchronized Planarity with Applications to Constrained Planarity Problems},
journal = {ACM Transactions on Algorithms},
year = {2023},
volume = {19},
number = {4},
pages = {1--23},
doi = {10.1145/3607474}
}
EUVIMED