Three types of geometric structure|grid triangulations, rectangular subdivisions, and orthogonal polyhedra| can each be described combinatorially by a regular la- beling: an assignment of colors and orientations to the edges of an associated maximal or near-maximal planar graph. We briey survey the connections and analogies between these three kinds of labelings, and their uses in designing ecient geometric algorithms. algorithm for drawing any maximal planar graph, using straight line edges, in an integer grid of linear dimensions (34). A key tool in Schnyder's re- sult is a regular labeling of the edges of the graph by colors and orientations, satisfying local constraints on how the edges incident to individual vertices can be la- beled. Soon after Schnyder's work, Kant and He (21, 24) showed that rectangular partitions of a rectangle into smaller rectangles could also be described as a regu- lar labeling, with dierent local constraints. More re- cently with Elena Mumford we showed that another kind of regular labeling describes orthogonal polyhedra in which three perpendicular edges meet at each ver- tex (11). Each of these labelings may be used algorithmi- cally to eciently construct the structures it describes. There are many strong analogies between these three types of labeling: each involves a maximal or near- maximal planar graph with a designated outer face and can be described as a coloring and orientation of the graph's edges. In each case local constraints at the ver- tices automatically ensure the acyclicity of certain sub- graphs derived from the labeling. And, in each case, the set of labelings of a xed graph forms a distribu- tive lattice in which adjacent lattice elements are re- lated by local twisting operations. However the reasons that these three kinds of geometric object should be described combinatorially in such similar ways to each other are not well understood. In this paper we survey these three types of regular labeling, their properties, and their applications, with the hope that bringing this material together will bring to light further connections between these problems.
['David Eppstein']
Regular Labelings and Geometric Structures