Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00135 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 |
Journal of Graph Algorithms and Applications |