Planar graphs, and more generally graphs embedded on surfaces, arise in applications such as road map navigation and logistics, computational topol­ogy, 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 dis­covered 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 will bring 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, multicom­modity flow, variants of shortest paths, Gomory-Hu cut trees, global min-cut, k-terminal 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 cer­tain 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, 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).

• Mohammad Hossein Bateni (Google - New York, US) [dblp]
• Ivona Bezáková (Rochester Institute of Technology, US) [dblp]
• Therese Biedl (University of Waterloo, CA) [dblp]
• Glencora Borradaile (Oregon State University, US) [dblp]
• Sergio Cabello (University of Ljubljana, SI) [dblp]
• Éric Colin de Verdière (ENS - Paris, FR) [dblp]
• Sabine Cornelsen (Universität Konstanz, DE) [dblp]
• Arnaud de Mesmay (ENS - Paris, FR) [dblp]
• Frederic Dorn (SINTEF - Trondheim, NO) [dblp]
• Alina Ene (University of Illinois - Urbana-Champaign, US) [dblp]
• Jeff Erickson (University of Illinois - Urbana-Champaign, US) [dblp]
• Jittat Fakcharoenphol (Kasetsart University - Bangkok, TH) [dblp]
• Kyle Jordan Fox (University of Illinois - Urbana-Champaign, US) [dblp]
• Petr A. Golovach (University of Bergen, NO) [dblp]
• Michelangelo Grigni (Emory University, US) [dblp]
• MohammadTaghi Hajiaghayi (University of Maryland - College Park, US) [dblp]
• Marcin Kaminski (University of Warsaw, PL) [dblp]
• Philip N. Klein (Brown University - Providence, US) [dblp]
• Yusuke Kobayashi (University of Tokyo, JP) [dblp]
• Nitish Korula (Google - New York, US) [dblp]
• Daniel Lokshtanov (University of Bergen, NO) [dblp]
• Dániel Marx (Hungarian Academy of Sciences - Budapest, HU) [dblp]
• Claire Mathieu (Brown University - Providence, US) [dblp]
• Tamara Mchedlidze (KIT - Karlsruher Institut für Technologie, DE) [dblp]
• Matthias Mnich (Universität des Saarlandes, DE) [dblp]
• Shay Mozes (Interdisciplinary Center Herzliya, IL) [dblp]
• Matthias Müller-Hannemann (Martin-Luther-Universität Halle-Wittenberg, DE) [dblp]
• Amir Nayyeri (University of Illinois - Urbana-Champaign, US) [dblp]
• Rolf Niedermeier (TU Berlin, DE) [dblp]
• Yahav Nussbaum (Tel Aviv University, IL) [dblp]
• Marcin Pilipczuk (University of Warsaw, PL) [dblp]
• Michal Pilipczuk (University of Bergen, NO) [dblp]
• Peter Rossmanith (RWTH Aachen, DE) [dblp]
• Ignaz Rutter (KIT - Karlsruher Institut für Technologie, DE) [dblp]
• Saket Saurabh (The Institute of Mathematical Sciences, IN) [dblp]
• Anastasios Sidiropoulos (University of Illinois - Urbana-Champaign, US) [dblp]
• Erik Jan van Leeuwen (MPI für Informatik - Saarbrücken, DE) [dblp]
• Oren Weimann (University of Haifa, IL) [dblp]
• Erin Moriarty Wolf Chambers (St. Louis University, US) [dblp]
• Christian Wulff-Nilsen (University of Copenhagen, DK) [dblp]