Tech Report CS-94-46

Optimal Upward Planarity Testing of Single-Source Digraphs

Paola Bertolazzi, Carlo Mannino, Giuseppe Di Battista, and Roberto Tamassia

December 1994


A digraph is upward planar if it has a planar drawing such that all the edges are monotone with respect to the vertical direction. Testing upward planarity and constructing upward planar drawings is important for displaying hierarchical network structures, which frequently arise in software engineering, project management, and visual languages. In this paper we investigate upward planarity testing of single-source digraphs: we provide a new combinatorial characterization of upward planarity, and give an optimal algorithm for upward planarity testing. Our algorithm tests whether a single-source digraph with $n$ vertices is upward planar in $O(n)$ sequential time, and in $O(\log n)$ time on a CRCW PRAM with $n \log\log n / \log n$ processors, using $O(n)$ space. The algorithm also constructs an upward planar drawing if the test is successful. The previous best result is an $O(n^2)$-time algorithm by Hutton and Lubiw. No efficient parallel algorithms for upward planarity testing were previously known.

(complete text in pdf or gzipped postscript)