The (3,1)-ordering for 4-connected planar triangulations
Therese Biedl and Martin Derka
Vol. 20, no. 2, pp. 347-362, 2016. Regular paper.
Abstract Canonical orderings of planar graphs have frequently been used in graph drawing and other graph algorithms. In this paper we introduce the notion of an $(r,s)$-canonical order, which unifies many of the existing variants of canonical orderings. We then show that $(3,1)$-canonical ordering for 4-connected triangulations always exist; to our knowledge this variant of canonical ordering was not previously known. We use it to give much simpler proofs of two previously known graph drawing results for 4-connected planar triangulations, namely, rectangular duals and rectangle-of-influence drawings.
Submitted: November 2015.
Reviewed: April 2016.
Revised: May 2016.
Accepted: May 2016.
Final: June 2016.
Published: June 2016.
Communicated by Giuseppe Liotta
article (PDF)