To access the full text documents, please follow this link: http://hdl.handle.net/2117/8923

Binary labelings for plane quadrangulations and their relatives
Felsner, Stefan; Huemer, Clemens; Kappes, Sarah; Orden, David
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta
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.
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Combinatòria
Combinatorial analysis
Graph theory
Schnyder labeling
Quadrangulation
Book embedding
Pseudo-triangulation
Laman graph
Anàlisi combinatòria
Grafs, Teoria de
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
info:eu-repo/semantics/publishedVersion
Article
         

Show full item record

Related documents

Other documents of the same author

Felsner, Stefan; Fusy, Éric; Noy Serrano, Marcos; Orden, David
Felsner, Stefan; Huemer, Clemens; Saumell Mendiola, Maria
Fabila-Monroy, Ruy; Huemer, Clemens; Tramuns, Eulàlia
Fabila Monroy, Ruy; Huemer, Clemens; Mitsche, Dieter
Fabila-Monroy, Ruy; Huemer, Clemens; Mitsche, Dieter
 

Coordination

 

Supporters