Building Blocks of Upward Planar Digraphs - Healy, Patrick; Lynch, Karol (Journal of Graph Algorithms and Applications, 2007)
The upward planarity testing problem consists of testing if adigraph admits a drawing Γ such that all edges in Γ aremonotonically increasing in the vertical direction and no edges inΓ cross. In this paper we reduce the problem of testing adigraph for upward planarity to the problem of testing if itsblocks admit upward planar drawings with certainproperties. We also show how to test if a block of a digraph admitsan upward planar drawing with the aforementioned properties. <!---->