Binary Labelings for Plane Quadrangulations and their Relatives

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity, 12 (3), pp.115-138
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00993747
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 20 mai 2014 - 16:00:11
Dernière modification le : samedi 16 décembre 2017 - 07:18:04
Document(s) archivé(s) le : mercredi 20 août 2014 - 11:50:59

Fichier

976-5549-1-PB.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-00993747, version 1

Collections

Citation

Stefan Felsner, Clemens Huemer, Sarah Kappes, David Orden. Binary Labelings for Plane Quadrangulations and their Relatives. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity, 12 (3), pp.115-138. 〈hal-00993747〉

Partager

Métriques

Consultations de la notice

269

Téléchargements de fichiers

348