http://www.dagstuhl.de/13421

October 13 – 18 , 2013, Dagstuhl Seminar 13421

Algorithms for Optimization Problems in Planar Graphs

Organizers

Glencora Borradaile (Oregon State University, US)
Philip N. Klein (Brown University – Providence, US)
Dániel Marx (Hungarian Academy of Sciences – Budapest, HU)
Claire Mathieu (Brown University – Providence, US)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 3, Issue 10 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents
Dagstuhl's Impact: Documents available

Summary

Planar graphs, and more generally graphs embedded on surfaces, arise in applications such as road map navigation and logistics, computational topology, graph drawing, and image processing. There has recently been a growing interest in addressing combinatorial optimization problems using algorithms that exploit embeddings on surfaces to achieve provably higher-quality output or provably faster running times. New algorithmic techniques have been discovered that yield dramatic improvements over previously known results. In addition, results have been generalized to apply to other families of graphs: excluded-minor, bounded-genus and bounded-treewidth graphs.

This Dagstuhl seminar brought together researchers who have been working in these areas to present recent research results, consolidate and share understanding of the emerging basic techniques, and collaborate to move past the current barriers.

  • Polynomial-time solvable problems. There is a long tradition of finding fast algorithms for poly-time problems in planar graphs. In 1956, the first paper on maximum $st$-flow addressed the case where the network is planar (and $s$ and $t$ are adjacent). In 1976, a linear-time algorithm was given for minimum spanning trees in planar graphs. In 1979, the paper introducing generalized nested dissection gave a fast algorithm for shortest paths in planar graphs with positive and negative lengths. The past couple of decades has witnessed the discovery of fast algorithms for a wide range of polynomial-time problems in planar graphs: variants of max flow, multicommodity flow, variants of shortest paths, Gomory-Hu cut trees, global min-cut, girth, matching, and min-cost flow. It seems, however, there is a long way yet to go; for many promising problems, no planarity-exploiting algorithm is known or there is reason to believe faster algorithms can be obtained.
  • Approximation schemes. Research on polynomial-time approximation schemes (PTAS) for optimization problems in planar graphs goes back to the pioneering work of Lipton and Tarjan (1977) and Baker (1983), who introduced linear-time algorithms for certain problems in which the constraints were quite local, e.g. maximum-weight independent set and minimum-weight dominating set. For many years, little progress was made on problems with non-local constraints. In the mid-nineties, polynomial-time approximation schemes were developed for the traveling-salesman problem (TSP) in planar graphs, but in these the degree of the polynomial running time depended on the desired accuracy. A decade later, a linear-time approximation scheme was found for TSP. Shortly afterwards, the first polynomial time approximation schemes were found for problems, e.g. Steiner tree, in which the solution was much smaller than the input graph. Since then approximation schemes have been found for several other problems in planar graphs, such as two-connected spanning subgraph, Steiner forest, survivable network design, k-terminal cut, and k-center. Important new techniques have emerged, but we still lack fast approximation schemes for many important problems (e.g. facility location). The area of approximation schemes for planar graphs is ripe for further exploration.
  • Fixed-parameter tractable algorithms. Another way to cope with computational intractability of some planar graph problems is through the lens of fixed-parameter tractability. The theory of bidimensionality and algorithms exploiting tree decompositions of planar graphs give a general methodology of dealing with planar problems. One way to obtain fixed-parameter tractability results is to show that there is a polynomial-time preprocessing algorithm that creates a "problem kernel" by reducing the size of the instance such that it is bounded by a function of the parameter $k$. Research on kernelization for planar graph problems has been a very active topic recently, culminating in a meta-theorem that gives problem kernels for a wide range of problems (2009).

The scientific program of the seminar consisted of 24 talks. Five of these talks were longer (60-90 minute) tutorials overviewing the three main areas of the seminar: Jeff Erickson ("Flows in planar and surface graphs") and Christian Wulff-Nilsen ("Separators in planar graphs with applications") covered polynomial-time algorithms; Philip Klein ("Some techniques for approximation schemes on planar graphs") covered approximation schemes; and Dániel Marx ("The square-root phenomenon in planar graphs") and Daniel Lokshtanov ("Kernels for planar graph problems") covered fixed-parameter tractability. One of the main goals of the seminar was to encourage collaboration between the three communities, and these well-received tutorials were very helpful by introducing the basics of each of these topics. The rest of the talks were 25-minute presentations on recent research of the participants.

In this talk, I will present two results that are close, in that they maintain some graph parameters that are closely related to the optimal height of a planar drawing. Namely, I will show how to triangulate a planar graph such that the outer-planarity remains (roughly) the same, and I will show how to triangulate a planar graph such that the pathwidth remains (asymptotically) the same.

License
  Creative Commons BY 3.0 Unported license
  Glencora Borradaile, Philip N. Klein, Dániel Marx, and Claire Mathieu

Related Dagstuhl Seminar

Classification

  • Data Structures / Algorithms / Complexity

Keywords

  • Algorithms
  • Combinatorial optimization
  • Planar graphs
  • Graphs
  • Approximation algorithms
  • Fixed-parameter tractability

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

NSF young researcher support