Upward Planar Drawings and Switch-regularity Heuristics
Vol. 10, no. 2, pp. 259-285, 2006. Regular paper.
Abstract In this paper we present a new characterization of switch-regular upward embeddings, a concept introduced by Di Battista and Liotta in 1998. This characterization allows us to define a new efficient algorithm for computing upward planar drawings of embedded planar digraphs. If compared with a popular approach described by Bertolazzi, Di Battista, Liotta, and Mannino, our algorithm computes drawings that are significantly better in terms of total edge length and aspect ratio, especially for low-density digraphs. Also, we experimentally prove that the running time of the drawing process is reduced in most cases.
Submitted: March 2005.
Revised: March 2006.
Communicated by Michael Kaufmann
article (PDF)