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 uncapacitated facility 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.
