Stefan Felsner ; Clemens Huemer ; Sarah Kappes ; David Orden - Binary Labelings for Plane Quadrangulations and their Relatives

dmtcs:475 - Discrete Mathematics & Theoretical Computer Science, January 1, 2011, Vol. 12 no. 3 - https://doi.org/10.46298/dmtcs.475
Binary Labelings for Plane Quadrangulations and their RelativesArticle

Authors: Stefan Felsner 1; Clemens Huemer 2; Sarah Kappes 1; David Orden ORCID3

  • 1 Institut für Mathematik [Berlin]
  • 2 Applied Mathematics IV Department
  • 3 Departamento de Matemáticas - UAH

Motivated by the bijection between Schnyder labelings of a plane triangulation and partitions of its inner edges into three trees, we look for binary labelings for quadrangulations (whose edges can be partitioned into two trees). Our labeling resembles many of the properties of Schnyder's one for triangulations: Apart from being in bijection with tree decompositions, paths in these trees allow to define the regions of a vertex such that counting faces in them yields an algorithm for embedding the quadrangulation, in this case on a 2-book. Furthermore, as Schnyder labelings have been extended to 3-connected plane graphs, we are able to extend our labeling from quadrangulations to a larger class of 2-connected bipartite graphs.


Volume: Vol. 12 no. 3
Section: Graph and Algorithms
Published on: January 1, 2011
Imported on: March 26, 2015
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 505 times.
This article's PDF has been downloaded 598 times.