On the computational complexity of upward and rectilinear planarity testing

Citation
A. Garg et R. Tamassia, On the computational complexity of upward and rectilinear planarity testing, SIAM J COMP, 31(2), 2001, pp. 601-625
Citations number
35
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
2
Year of publication
2001
Pages
601 - 625
Database
ISI
SICI code
0097-5397(20011011)31:2<601:OTCCOU>2.0.ZU;2-E
Abstract
A directed graph is upward planar if it can be drawn in the plane such that every edge is a monotonically increasing curve n the vertical direction an d no two edges cross. An undirected graph is rectilinear planar if it can b e drawn in the plane such that every edge is a horizontal or vertical segme nt and no two edges cross. Testing upward planarity and rectilinear planari ty are fundamental problems n the effective visualization of various graph and network structures. For example, upward planarity is useful for the dis play of order diagrams and subroutine-call graphs, while rectilinear planar ity 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 m inimum number of bends in a planar orthogonal drawing of an n-vertex graph with an O(n(1-epsilon)) error for any epsilon > 0.