On the Computational Complexity of Upward and Rectilinear Planarity Testing

Garg, 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. 286-297(Official URL: http://dx.doi.org/10.1007/3-540-58950-3_384).

Full text not available from this repository.

Abstract

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(n^{1-\epsilon}) error, for any \epsilon \geq 0.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-58950-3_384
Classifications: G Algorithms and Complexity > G.770 Planarity Testing
URI: http://gdea.informatik.uni-koeln.de/id/eprint/194

Actions (login required)

View Item View Item