A planar graph is a network drawn on the plane so that no edges cross. Planar and near-planar graphs have been fertile ground for algorithms research since the mid-1950s, both because they naturally model many classes of networks that arise in practice, and because they admit simpler and faster algorithms than more general graphs.  Algorithms for such graphs find numerous applications in geographic information systems, computer graphics, solid modeling, computer vision, VLSI design, information visualization, finite-element mesh generation, computational geometry, and other areas.  New techniques introduced in the last ten years have led to an explosion of new optimization algorithms for planar graphs and their generalizations, as well as the emergence of a small but growing research community that draws on and contributes to this pool of techniques; however, we are coming up against limitations of these techniques.
The goal of this project is to develop efficient algorithms for several fundamental optimization problems in planar graphs and related graph families.  Working on problems just outside the range of existing tools will lead the PIs toward developing the next batch of techniques that will maintain momentum in the field.  Specific targets include faster and simpler exact algorithms for variants of shortest paths, maximum flows, minimum cuts, and minimum-cost flows, as well as new polynomial-time approximation schemes for several network design, clustering, and facility location problems for which no such schemes are currently known.  The PIs will also implement and experimentally evaluate some algorithms that appear particularly promising, and make the resulting software publicly available, to support the efforts of students, researchers, and professionals in many different areas of computing.
