论文标题
同步的平面性与应用程序的应用程序有限问题
Synchronized Planarity with Applications to Constrained Planarity Problems
论文作者
论文摘要
我们介绍了问题同步的平面度。粗略地说，它的输入是无环的多画像，以及同步约束，例如，通过在其边缘之间提供两次试验，即相同程度的匹配对顶点。然后，同步平面性询问该图是否允许无交叉嵌入到平面中，以使同步顶点周围的边缘顺序保持一致。一方面，我们表明可以在二次时期解决同步平面，另一方面，它是一种强大的建模语言，使我们可以轻松地制定一些有限的平面问题作为同步平面性的实例。特别是，这使我们能够在二次时间求解聚类的平面度，在二次时期，最有效的先前已知算法的上限为$ o（n^{8}）$。
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})$.
