On the computational complexity of upward and rectilinear planarity testing

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.