Building Blocks of Upward Planar Digraphs
Patrick Healy and Karol Lynch
Vol. 11, no. 1, pp. 3-44, 2007. Regular paper.
Abstract The upward planarity testing problem consists of testing if a digraph admits a drawing Γ such that all edges in Γ are monotonically increasing in the vertical direction and no edges in Γ cross. In this paper we reduce the problem of testing a digraph for upward planarity to the problem of testing if its blocks admit upward planar drawings with certain properties. We also show how to test if a block of a digraph admits an upward planar drawing with the aforementioned properties.
Submitted: May 2005.
Revised: August 2006.
Communicated by Giuseppe Di Battista
article (PDF)