OPTIMAL UPWARD PLANARITY TESTING OF SINGLE-SOURCE DIGRAPHS

A digraph is upward planar if it has a planar drawing such that all th e edges are monotone with respect to the vertical direction. Testing u pward planarity and constructing upward planar drawings is important f or 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 di graphs; we provide a new combinatorial characterization of upward plan arity and give an optimal algorithm for upward planarity testing. Our algorithm tests whether a single-source digraph with n vertices is upw ard planar in O(n) sequential time, and in O(log n) time on a CRCW PRA M 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. T he previously known best result is an O(n(2))-time algorithm by Hutton and Lubiw [Proc. 2nd ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 1991, pp. 203-211]. No efficient parallel algorithms fo r upward planarity testing were previously known.