Irrelevant Vertices for the Planar Disjoint Paths Problem

The Disjoint Paths Problem asks, given a graph G and a set of pairs of terminals (s1, t1),..., (sk, tk), whether there is a collection of k pairwise vertex-disjoint paths linking si and ti, for i = 1,..., k. In their f(k) · n3 algorithm for this problem, Robertson and Seymour 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. This fact is based on the celebrated Unique Linkage Theorem, whose – very technical – proof gives a function g(k) that is responsible for an immense parameter dependence in the running time of the algorithm. In this paper we prove this result for planar graphs achieving g(k) = 26 ·k3/2 · 2k. Our bound is radically better than the bounds known for general graphs. Moreover, our proof is new and self-contained, and it strongly exploits the combinatorial properties of planar graphs