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

平面图是在平面上绘制的网络，因此没有边交叉。自20世纪50年代中期以来，平面图和近平面图一直是算法研究的沃土，这既是因为它们自然地模拟了实践中出现的许多类别的网络，也是因为它们比更一般的图更简单，更快的算法。 此类图的算法在地理信息系统、计算机图形学、实体建模、计算机视觉、超大规模集成电路设计、信息可视化、有限元网格生成、计算几何和其他领域有许多应用。 在过去的十年中引入的新技术已经导致了平面图及其推广的新优化算法的爆炸，以及一个小型但不断增长的研究社区的出现，该社区借鉴并有助于这一技术池;然而，我们遇到了这些技术的局限性。这个项目的目标是为平面图和相关图族中的几个基本优化问题开发有效的算法。 解决现有工具范围之外的问题将引导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.