
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 ).
ddc:004, FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Analysis of algorithms and problem complexity, DATA processing & computer science, Constrained Planarity, 004, atomic embeddability, Atomic Embeddability, Cluster Planarity, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), constrained planarity, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Planarity Testing, info:eu-repo/classification/ddc/004, cluster planarity, planarity testing, Computer Science - Discrete Mathematics
ddc:004, FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Analysis of algorithms and problem complexity, DATA processing & computer science, Constrained Planarity, 004, atomic embeddability, Atomic Embeddability, Cluster Planarity, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), constrained planarity, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Planarity Testing, info:eu-repo/classification/ddc/004, cluster planarity, planarity testing, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 6 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
