On the Computational Complexity of Upward and Rectilinear Planarity TestingGarg, Ashim and Tamassia, Roberto (1995) On the Computational Complexity of Upward and Rectilinear Planarity Testing. In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994 , pp. 286297(Official URL: http://dx.doi.org/10.1007/3540589503_384). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540589503_384
AbstractA 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 NPcomplete problems. We also show that it is NPhard to approximate the minimum number of bends in a planar orthogonal drawing of an nvertex graph with an o(n^{1\epsilon}) error, for any \epsilon \geq 0.
Actions (login required)
