2015/11/03 by Therese Biedl, Biedl, Therese, Martin Derka +1
Computer Science · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #G.2.2 #I.3.5 #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1511.00873
arxiv created 2015/11/03 · arxiv updated 2015/11/04
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.