  Many problems in computational geometry are not stated in graph-theoretic
terms, but can be solved efficiently by constructing an auxiliary graph and
performing a graph-theoretic algorithm on it. Often, the efficiency of the
algorithm depends on the special properties of the graph constructed in this
way. We survey the art gallery problem, partition into rectangles,
minimum-diameter clustering, rectilinear cartogram construction, mesh
stripification, angle optimization in tilings, and metric embedding from this
perspective.
