Please use this identifier to cite or link to this item:
http://hdl.handle.net/2117/3013
|
| Title: | 4-labelings and grid embeddings of plane quadrangulations |
| Authors: | Barrière, Lali
Huemer, Clemens |
| Other authors: | Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV
Universitat Politècnica de Catalunya. COMBGRAF - Combinatòria, Teoria de Grafs i Aplicacions
Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta |
| Keywords: | Àrees temàtiques de la UPC::Matemàtiques i estadística
Graph theory
embedding
labeling
quadrangulation
rectangle of influence
rectangulation
planar bipartite graph
Grafs, Teoria de
Classificació AMS::05 Combinatorics::05C Graph theory |
| Abstract: | We show that each quadrangulation on $n$ vertices has a closed rectangle of influence drawing on the $(n-2) \times (n-2)$ grid. Further, we present a simple algorithm to obtain a straight-line drawing of a quadrangulation on the $\Big\lceil\frac{n}{2}\Big\rceil \times \Big\lceil\frac{3n}{4}\Big\rceil$ grid. This is not optimal but has the advantage over other existing algorithms that it is not needed to add edges to the quadrangulation to make it $4$-connected. The algorithm is based on angle labeling and simple face counting in regions analogous to Schnyder's grid embedding for triangulation. This extends previous results on book embeddings for quadrangulations from Felsner, Huemer, Kappes, and Orden (2008).Our approach also yields a representation of a quadrangulation as a pair of rectangulations with a curious property. |
| Appears in Collections: | Documents de recerca
|
|
