Upward Planar Drawings and Switch-regularity Heuristics - Didimo, Walter (Journal of Graph Algorithms and Applications, 2006)
In this paper we present a new characterization ofswitch-regular upward embeddings, a concept introducedby Di Battista and Liotta in 1998. This characterizationallows us to define a new efficient algorithm for computing upward planardrawings of embedded planar digraphs. If comparedwith a popular approach described by Bertolazzi, Di Battista, Liotta, and Mannino,our algorithm computes drawingsthat are significantly better in terms of total edge lengthand aspect ratio, especially for low-density digraphs.Also, we experimentally prove that the running timeof the drawing process is reduced in most cases. <!---->