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.