Authors

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.