Exploiting Planarity in Optimization Algorithms

平面图是可以在平面上绘制的没有交叉的图形。这种图形自然出现在图像处理、路线图中的物流和VLSI等应用领域。在解决图上的基本优化问题时，如果可以假设输入图是平面的，则可以使用比不需要此假设的算法更快和/或更准确的算法。本研究涉及设计和分析这些利用平面性的基本优化问题算法。这一领域的进步可以改善解决路线图问题的方法，如路由、网络设计和设施位置，以及解决图像处理问题，如分割和跟踪。这项研究包括两个重点。第一个目标是发现NP-hard图问题的多项式时间逼近方案，如斯坦纳树、多终端切割、度量标记和无电容设施位置。该方法是在将图的树宽度减小到较小的情况下，找到近似保持目标的边删除和边收缩，然后在低树宽度图中最优地解决问题，然后将解提升到原始图。第二个目标是为一些基本的多项式时间问题，如流动问题，发现简单有效的算法。该方法涉及指定一个支点规则，该支点规则使网络单纯形的迭代次数很少。该算法“扫描”整个图，类似于扫描线算法在平面上解决问题的方式。

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.