AF: Medium: Collaborative Research: Fast and accurate optimization in planar graphs and beyond

平面图是在平面上绘制的网络，因此没有边相交。自20世纪50年代中期以来，平面图和近平面图一直是算法研究的沃土，这既是因为它们自然地对实践中出现的许多类网络进行建模，也是因为它们允许比更一般的图更简单、更快的算法。这类图形的算法在地理信息系统、计算机图形学、实体建模、计算机视觉、VLSI设计、信息可视化、有限元网格生成、计算几何等领域有着广泛的应用。过去十年中引入的新技术导致了平面图及其推广的新优化算法的爆炸性增长，以及利用并促进这一技术池的小型但不断增长的研究社区的出现；然而，我们遇到了这些技术的局限性。这个项目的目标是为平面图和相关图族中的几个基本优化问题开发有效的算法。解决现有工具范围之外的问题将导致PI开发下一批将在该领域保持势头的技术。具体目标包括更快、更简单的最短路径、最大流、最小割和最小费用流的变体的精确算法，以及用于几个网络设计、集群和设施选址问题的新的多项式时间近似方案，这些问题目前尚不知道此类方案。PI还将实施和试验性地评估一些似乎特别有希望的算法，并将生成的软件公开提供，以支持学生、研究人员和专业人员在许多不同计算领域的努力。

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.