Upward Planar Drawings of Series-Parallel Digraphs with Maximum Degree Three.
Md. Abul Hassan Samee, Md. Saidur Rahman · Workshop on Algorithms and Computation · 2007
An upward planar drawing of a digraph G is a planar drawing of G where every edge is drawn as a simple curve monotone in the vertical direction. A digraph is upward planar if it has an embedding that admits an upward planar drawing. The problem of testing whether a digraph is upward planar is NP-complete. In this paper we give a linear-time algorithm to test the upward planarity of a series-parallel digraph G with maximum degree three and obtain an upward planar drawing of G if G admits one.