Originators: Clemens Huemer and Sarah Kappes (presented by Michelle Delcourt - REGS 2011)
Definitions: A triangulation is a simple plane graph where every face boundary is a 3-cycle. A quadrangulation is a 2-connected plane graph where every face boundary is a 4-cycle. (In a near-triangulation or near-quadrangulation, the unbounded face may have a different length.) A graph G with n vertices and m edges is a Laman graph if m=2n-3 and every subgraph induced by k vertices (where k>1) contains at most 2k-3 edges. A plane straight-line graph G is pointed if all vertices in V(G) have an incident reflex angle. A pointed pseudo-triangulation is a maximal pointed plane straight-line graph (face-boundaries may have length greater than 3).
Background: A planar graph is embedded on a grid of order k when its vertices are located at elements of [k]² in the plane and its edges are drawn as line segments. The embedding is convex if each face boundary is a convex polygon. Schnyder [S] proved that every n-vertex planar graph embeds on an grid of order n-2 (see [T1] and [T2] for the details). Felsner [F1,F2] proved that every 3-connected planar graph with f faces has a convex embedding on an grid of order f-1. Biedl and Brandenburg [BB] proved that every n-vertex planar bipartite graph embeds on a grid of order ⌊n/2⌋.
Motivated by Schnyder labelings, the technique used in [S], Huemer and Kappes defined an analogous binary labeling (see [HK]) and studied its use on quadrangulations and plane Laman graphs. For quadrangulations the labeling yields a decomposition into two edge-disjoint spanning trees, but for plane Laman graphs it does not necessarily yield such a decomposition. Nevertheless, every pointed pseudo-triangulation is a Laman graph, and every planar Laman graph can be realized as a pointed pseudo-triangulation.
Question 1: (Huemer and Kappes [HK]) What is the smallest grid on which every n-vertex planar Laman graph has a straight-line embedding?
Question 2: (Haas et al. [H], restated by [HK]) Can every n-vertex planar Laman graph be embedded on a grid of small size as a pseudo-triangulation?
Comments: Schnyder labelings have also been called "realizers", "Schnyder woods", "Schnyder tree decomposition", "Schnyder edge-colorings", etc. For the definition, properties, and applications of Schnyder labelings see http://www.math.tu-berlin.de/diskremath/research/schnyder.html.
References:
[BB] Therese Biedl and Franz J. Brandenburg, 2005.
Drawing planar bipartite graphs with small area. In Proc. 17th Canadian
Conf. on Comp. Geom. (2005), 105-108.
[F1] Stefan Felsner, Convex drawings of Planar Graphs and the Order Dimension of 3-Polytopes, Order, Volume 18 (2000), available at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.7529.
[F2] Stefan Felsner, Geometric Graphs and Arrangements, Vieweg & Verlag (2004), 17-37.
[H] R. Haas, D. Orden, G. Rote, F. Santos, B. Servatius, H. Servatius, D. Souvaine, I. Streinu, W. Whiteley. Planar minimally rigid graphs and pseudo-triangulations. Computational Geometry, Theory and
Applications 31:31–61, 2005., available at http://www.cs.tufts.edu/research/geometry/pdf/haas04planar.pdf.
[HK] Clemens Huemer and Sarah Kappes, A binary labelling for plane Laman graphs and quadrangulations, European Workshop on Computational Geometry (2006), available at http://eurocg.org/06/delaunay.tem.uoc.gr/~mkaravel/ewcg06/papers/20.pdf.
[S] Walter Schnyder, Embedding planar graphs on the grid, In Proc. 1st ACM-SIAM Symp. on Discrete Algorithms, (1990) 138-148.
[T1] William T. Trotter, Combinatorics and Partially Ordered Sets, Johns Hopkins University Press (1992), 127-155.
[T2] William T. Trotter, Planar Graphs and Planar Posets - II, talk on September 3, 2009,
available at http://people.math.gatech.edu/~trotter/GraphTheorySeminar-Part-2-2009.pdf.