A graph is rectilinear planar if it admits a planar orthogonal drawing without bends. While testing rectilinear planarity is NP-hard in general, it is a long-standing open problem to establish a tight upper bound on its complexity for partial 2-trees, i.e., graphs whose biconnected components are series-parallel. We describe a new $O(n^2 \log^2 n)$-time algorithm to test rectilinear planarity of partial 2-trees, which improves over the current best bound of $O(n^3 \log n)$. Moreover, for series-parallel graphs where no two parallel-components share a pole, we are able to achieve optimal $O(n)$-time complexity. Our algorithms are based on an extensive study and a deeper understanding of the notion of orthogonal spirality, introduced in 1998 to describe how much an orthogonal drawing of a subgraph is rolled-up in an orthogonal drawing of the graph.
翻译:如果允许不弯曲的平面图则是一个直线图。 测试正线平面图一般是硬硬的 NP, 长期存在的问题是, 要对部分两棵树的复杂程度建立紧紧的上限, 也就是说, 图形, 其双连接组件是序列相联的图。 我们描述一个新的 $O (n) 2\ log2\ 2 n) 时间算法, 以测试部分两棵树的正线性平面图, 这比 $O (n) 3\log n 的当前最佳约束值更好。 此外, 对于没有两个平行构件共享一极的系列单线图, 我们能够达到最佳的 $O (n) 时间复杂性。 我们的算法是基于广泛研究和更深入地理解矩螺旋性概念, 于1998年引入该算法是为了描述在图形的正向绘图中滚动了多少次图的分形图。