Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00220 Upward Planarization Layout Markus Chimani , Carsten Gutwenger , Petra Mutzel , and Hoi-Ming Wong Vol. 15, no. 1, pp. 127-155, 2011. Regular paper Abstract Recently, we presented a new practical method for upward crossing minimization [], which clearly outperformed existing approaches for drawing hierarchical graphs in that respect. The outcome of this method is an upward planar representation (UPR), a planarly embedded graph in which crossings are represented by dummy vertices. However, straight-forward approaches for drawing such UPRs lead to quite unsatisfactory results. In this paper, we present a new algorithm for drawing UPRs that greatly improves the layout quality, leading to good hierarchal drawings with few crossings. We analyze its performance on well-known benchmark graphs and compare it with alternative approaches.
|
Published: February 2011. Submitted: December 2009. Final: November 2010. Reviewed: August 2010. Revised: August 2010. Accepted: November 2010. Communicated by David Eppstein and Emden Gansner |
| Journal of Graph Algorithms and Applications |