The aim of this research is to develop new algorithms and algorithmic techniques for solving fundamental optimization problems on planar networks. Many optimization problems in networks are considered computationally difficult; some are even difficult to solve approximately. However, problems often become easier when the input network is restricted to be planar, i.e. when it can be drawn on the plane so that no edges cross each other. Such planar instances of optimization problems arise in several application areas, including logistics and route planning in road maps, image processing and computer vision, and VLSI chip design.
The investigators plan to develop algorithms that achieve faster running times or better approximations by exploiting the planarity of the input networks. In addition, in order to address the use of optimization in the discovery of some ground truth, the investigators will develop algorithms not just for the traditional worst-case input model but also for models in which there is an unusually good planted solution; for a model of this kind, the investigators expect to find algorithms that produce even more accurate answers.
The research will likely uncover new computational techniques whose applicability goes beyond planar networks. In the recent past, once a technique has been developed and understood in the context of planar networks, it has been generalized to apply to broader families of networks.
In addition, new algorithms and techniques resulting from this research might enable people to quickly compute better solutions to problems arising in diverse application areas. For example, research in this area has already had an impact in the computer vision community. Further research has the potential to be useful, for example, in the design of networks, the planning of routes in road maps, the processing of images.
