Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00219 More Canonical Ordering Melanie Badent , Ulrik Brandes , and Sabine Cornelsen Vol. 15, no. 1, pp. 97-126, 2011. Regular paper Abstract Canonical ordering is an important tool in planar graph drawing and other applications. Although a linear-time algorithm to determine canonical orderings has been known for a while, it is rather complicated to understand and implement, and the output is not uniquely determined. We present a new approach that is simpler and more intuitive, and that computes a newly defined leftist canonical ordering of a triconnected graph which is a uniquely determined leftmost canonical ordering. Further, we discuss duality aspects and relations to Schnyder woods.
|
Published: February 2011. Accepted: November 2010. Final: November 2010. Reviewed: August 2010. Submitted: December 2009. Revised: November 2010. Communicated by David Eppstein and Emden Gansner |
| Journal of Graph Algorithms and Applications |