The (3,1)-ordering for 4-connected planar triangulations - Biedl, Therese; Derka, Martin (Journal of Graph Algorithms and Applications, 2016)
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 ofcanonical orderings. We then show that $(3,1)$-canonical orderingfor 4-connected triangulations always exist; to our knowledgethis 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.