  The disjoint paths problem asks, given an graph G and k + 1 pairs of
terminals (s_0,t_0), ...,(s_k,t_k), whether there are k+1 pairwise disjoint
paths P_0, ...,P_k, such that P_i connects s_i to t_i. Robertson and Seymour
have proven that the problem can be solved in polynomial time if k is fixed.
Nevertheless, the constants involved are huge, and the algorithm is far from
implementable. The algorithm uses a bound on the tree-width of graphs with
vital linkages, and deletion of irrelevant vertices. We give single exponential
lower bounds both for the tree-width of planar graphs with vital linkages, and
for the size of the grid necessary for finding irrelevant vertices.
