2006 · 10 citations · 10 references
ComputingComputer ScienceMathematicsAlgorithmsDiscrete MathematicsGeometryDiscrete GeometryGeometric ConstructionsGeometric GraphsGraph AlgorithmsGraph LabelingGraph TheoryTriangulation AlgorithmsTriangulation GraphsTriangulationsVertex Labeling
We present binary labelings for the angles of quadrangulations and plane Laman graphs, which are in analogy with Schnyder labelings for triangulations [W. Schnyder, Proc. 1st ACM-SIAM Symposium on Discrete Algorithms, 1990] and imply a special tree decomposition for quadrangulations. In particular, we show how to embed quadrangulations on a 2-book, so that each page contains a non-crossing alternating tree.
10
On graphs and rigidity of plane skeletal structures
G. Laman · Journal of Engineering Mathematics · 1970 · 1.1K citations
Embedding planar graphs on the grid
Walter Schnyder · Symposium on Discrete Algorithms · 1990 · 577 citations
Convex Drawings of Planar Graphs and the Order Dimension of 3-Polytopes
Stefan Felsner · Order · 2001 · 123 citations