On the Computational Complexity of Upward and Rectilinear Planarity Testing
On the Computational Complexity of Upward and Rectilinear Planarity Testing
复制标题
关于向上和直线平面度测试的计算复杂性
DOI：
10.1137/s0097539794277123
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
R. Tamassia
中科院分区：
文献类型：
--
作者：
Ashim Garg;R. Tamassia
一个有向图是向上平面的，如果它可以在平面中画出，使得每条边在垂直方向上是单调递增的曲线，并且没有两条边相交。一个无向图是平面直线图，如果它可以在平面上画出，使得每条边都是水平或垂直的线段，并且没有两条边相交。测试向上平面性和直线平面性是各种图和网络结构的有效可视化中的基本问题。在本文中，我们表明，向上的平面性测试和直线平面性测试是NP完全问题。我们还证明了对于任意∈>0，以O（n1−∈）的误差近似n-顶点图的平面正交图中的最小弯曲数是NP-困难的。
A directed graph is upward planar if it can be drawn in the plane such that every edge is a monotonically increasing curve in the vertical direction, and no two edges cross. An undirected graph is rectilinear planar if it can be drawn in the plane such that every edge is a horizontal or vertical segment, and no two edges cross. Testing upward planarity and rectilinear planarity are fundamental problems in the effective visualization of various graph and network structures. In this paper we show that upward planarity testing and rectilinear planarity testing are NP-complete problems. We also show that it is NP-hard to approximate the minimum number of bends in a planar orthogonal drawing of an n-vertex graph with an O(n1−∈) error, for any ∈>0.