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^{8})$.
翻译:我们引入了同步计划性的问题。 粗略地说,它的投入是一个无循环的多面图,加上同步性制约,例如,通过在边缘之间提供一个双截线来匹配同等程度的脊椎对齐。 同步计划性然后问图是否承认在平面上存在一个无交叉嵌入的嵌入,这样同步计划性周围的边缘顺序是一致的。 我们一方面表明,同步计划性可以在二次时间中解决,另一方面,它作为一种强大的模型语言,让我们很容易地提出若干受制约的平面问题,作为同步计划性的例子。 特别是,这让我们在四面形时间解决集群计划性问题,在这种时候,最高效的先前已知算法的上限为$O( n ⁇ 8} $( $) 。