Special Issue on Selected Papers from the Seventeenth International Symposium on Graph Drawing, GD 2009
More Canonical Ordering
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.
Submitted: December 2009.
Reviewed: August 2010.
Revised: November 2010.
Accepted: November 2010.
Final: November 2010.
Published: February 2011.
Communicated by David Eppstein and Emden Gansner
article (PDF)