TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 13421

Algorithms for Optimization Problems in Planar Graphs

( Oct 13 – Oct 18, 2013 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/13421

Organizers

Contact



Motivation

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).


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.

Copyright Glencora Borradaile, Philip N. Klein, Dániel Marx, and Claire Mathieu

Participants
  • 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]

Related Seminars
  • Dagstuhl Seminar 16221: Algorithms for Optimization Problems in Planar Graphs (2016-05-29 - 2016-06-03) (Details)

Classification
  • data structures / algorithms / complexity

Keywords
  • algorithms
  • combinatorial optimization
  • planar graphs
  • graphs
  • approximation algorithms
  • fixed-parameter tractability