On the Computational Complexity of Upward and Rectilinear Planarity Testing
Authors:
- Ashim GargAGAshim Garg
- Roberto TamassiaRTRoberto Tamassia
- 1 January 2001
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 31 (2) , 601-625
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. For example, upward planarity is useful for the display of order diagrams and subroutine-call graphs, while rectilinear planarity is useful for the display of circuit schematics and entity-relationship diagrams. 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 > 0$.
Keywords
This publication has 29 references indexed in Scilit:
- Spirality and Optimal Orthogonal DrawingsSIAM Journal on Computing, 1998
- A better heuristic for orthogonal graph drawingsComputational Geometry, 1998
- Optimal Upward Planarity Testing of Single-Source DigraphsSIAM Journal on Computing, 1998
- Upward Planar Drawing of Single-Source Acyclic DigraphsSIAM Journal on Computing, 1996
- Upward drawings of triconnected digraphsAlgorithmica, 1994
- HOW TO DRAW A SERIES-PARALLEL DIGRAPHInternational Journal of Computational Geometry & Applications, 1994
- Algorithms for drawing graphs: an annotated bibliographyComputational Geometry, 1994
- Area requirement and symmetry display of planar upward drawingsDiscrete & Computational Geometry, 1992
- Bipartite graphs, upward drawings, and planarityInformation Processing Letters, 1990
- Algorithms for plane representations of acyclic digraphsTheoretical Computer Science, 1988