On Shortest Disjoint Paths in Planar Graphs

Yusuke Kobayashi and Christian Sommer

For a graph and a collection of vertex pairs, the disjoint paths problem is to find vertex-disjoint paths for each pair of nodes. In the corresponding optimization problem, the shortest disjoint path problem, the vertex-disjoint paths have to be chosen such that a given objective function is minimized. We consider two different objectives, namely minimizing the total path length (minimum sum, or short: min-sum), and minimizing the length of the longest path (min-max).

min-sum: We extend recent results by Colin de Verdière and Schrijver to prove that for a planar graph and for terminals adjacent to at most two faces, the Min-Sum 2 Disjoint Paths Problem can be solved in polynomial time. We also prove that for six terminals adjacent to one face in any order, the Min-Sum 3 Disjoint Paths Problem can be solved in polynomial time.

min-max: The Min-Max 2 Disjoint Paths Problem is known to be NP-hard for general graphs. We present an algorithm that solves the problem for graphs with tree-width 2 in polynomial time. We also close the gap between easy and hard instances by proving that the problem is weakly NP-hard for graphs with tree-width at least 3.

• Paper
• Technical Report

Bibtex

@inproceedings{conf/disc/KobayashiSommer09,
  author    = {Yusuke Kobayashi and
               Christian Sommer},
  title     = {On Shortest Disjoint Paths in Planar Graphs},
  booktitle = {Algorithms and Computation, 20th International Symposium,
               ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009.
               Proceedings},
  year      = {2009},
  pages     = {293--302}
}