Decompositions and Algorithms for the Disjoint Paths Problem in Planar Graphs

Submitted by admin on Fri, 08/03/2019 - 07:45
Giannos Stamoulis
Date of Defense
Three-member Committee
Michael C. Dracopoulos
Archontia C. Giannopoulou
Stavros Kolliopoulos (Advisor)

In the   Disjoint Paths Problem, given a graph G and  a set of k pairs of terminals, we ask whether the pairs of terminals can be linked by pairwise disjoint paths.
In the Graph Minors  series of 23 papers between 1984 and 2011, Neil Robertson and Paul D. Seymour, among other great results that heavily influenced Graph Theory, provided an f(k)*n^3 algorithm for the Disjoint Paths Problem. To achieve this, they introduced the  irrelevant vertex technique according to which in every instance  of  treewidth  greater  than g(k)  there is  an  “irrelevant”  vertex whose removal creates an equivalent instance of the problem.

We study the problem in planar graphs and we prove that for every fixed k every instance of the  Planar Disjoint Paths Problem can be transformed to an equivalent one that has bounded treewidth, by simultaneously discarding a set of vertices of the given planar graph. As a consequence  the  Planar Disjoint Paths Problem can be solved in linear time for every fixed number of terminals.