Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00396
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
|
Journal Supporters
|