Home | Issues | About JGAA | Instructions for Authors |
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.
|
Journal Supporters
|