  Three types of geometric structure---grid triangulations, rectangular
subdivisions, and orthogonal polyhedra---can each be described combinatorially
by a regular labeling: an assignment of colors and orientations to the edges of
an associated maximal or near-maximal planar graph. We briefly survey the
connections and analogies between these three kinds of labelings, and their
uses in designing efficient geometric algorithms.
