Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00127 Upward Planar Drawings and Switch-regularity Heuristics Walter Didimo 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 |
Journal of Graph Algorithms and Applications |