Exploiting Planarity in Optimization Algorithms

平面图是可以在没有交叉点的平面上绘制的图。这样的图形自然出现在图像处理、道路地图中的物流和VLSI等应用领域。在处理图上的基本优化问题时，如果输入的图可以假设为平面，则可以使用比不需要这种假设的算法更快和/或更准确的算法。本研究涉及对基本优化问题的这种平面性开发算法的设计和分析。这一领域的进展可能会导致解决道路地图问题(如路线选择、网络设计和设施选址)以及图像处理(如分割和跟踪)问题的方法的改进。第一个目标是寻找多项式时间近似方案来解决NP-Hard图问题，如Steiner树、多终端割、度量标号和无能力设施选址。该方法是在将图的树宽减少到一个较小的数目的同时，找到近似保持目标的边的删除和收缩，然后在低树宽的图中进行最优求解，然后将解提升到原始图。第二个重点是寻找简单有效的算法来解决一些基本的多项式时间问题，如流问题。该方法包括指定网络单形的迭代次数较少的枢轴规则。该算法“扫描”整个图形，类似于扫描线算法解决平面问题的方式。

Planar graphs are graphs that can be drawn on the plane with no crossings. Such graphs naturally arise in application areas such as image processing, logistics in road maps, and VLSI. In addressing fundamental optimization problems on graphs, if the input graphs can assumed to be planar, algorithms can be used that are faster and/or more accurate than algorithms that do not require this assumption.This research involves the design and analysis of such planarity-exploiting algorithms for fundamental optimization problems. Advances in this area could lead to improvements in methods for solving problems in road maps such as routing, network design, and facility location, and for solving problems in image processing such as segmentation and tracking.The research consists of two thrusts. The first aims to discover polynomial-time approximation schemes for NP-hard graph problems such as Steiner tree, multiterminal cut, metric labeling, and uncapacitatedfacility location. The approach is to find edge deletions and contractions that approximately preserve the objective while reducing the tree-width of the graph to a small number, then solving the problem optimally in the low-tree-width graph, then lifting the solution to the original graph. The second thrust aims to discover simple and efficient algorithms for some fundamental polynomial-time problems such as flow problems. The approach involves specifying a pivot rule for which the number of iterations of network simplex is small. The algorithm "sweeps" through the graph, analogous to the way a sweep-line algorithm solves a problem in the plane.