论文标题
平面串联平行图的直线平面测试线性时间
Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time
论文作者
论文摘要
平面图是直线平面，如果它允许嵌入嵌入的直线图，每个边缘都是水平或垂直的。我们证明，对于任何飞机系列 - 平行图$ g $，使用$ n $ dertices的任何飞机系列平行图$ g $可以以最佳$ o（n）$时间来解决直线平面测试。如果$ g $是直线平面，则可以用$ o（n）$时间来构建嵌入式保护的直线平面图。我们的结果是基于对直线平面串联平行图的表征，其组件可以具有的正交螺旋性的间隔，并且会导致可以轻松实现的算法。
A plane graph is rectilinear planar if it admits an embedding-preserving straight-line drawing where each edge is either horizontal or vertical. We prove that rectilinear planarity testing can be solved in optimal $O(n)$ time for any plane series-parallel graph $G$ with $n$ vertices. If $G$ is rectilinear planar, an embedding-preserving rectilinear planar drawing of $G$ can be constructed in $O(n)$ time. Our result is based on a characterization of rectilinear planar series-parallel graphs in terms of intervals of orthogonal spirality that their components can have, and it leads to an algorithm that can be easily implemented.
