On the Computational Complexity of Upward and Rectilinear Planarity Testing

TLDR

Upward planarity requires a directed graph to be drawn with monotonically increasing vertical edges without crossings, while rectilinear planarity requires an undirected graph to be drawn with horizontal or vertical edges without crossings, and both problems are key for visualizing structures such as order diagrams, call graphs, circuit schematics, and entity‑relationship diagrams. We prove that testing upward planarity and rectilinear planarity are NP‑complete, and that approximating the minimum number of bends in a planar orthogonal drawing within an \(O(n^{1-\varepsilon})\) factor is NP‑hard for any \(\varepsilon>0\).

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$.