The Vertex-Disjoint Menger Problem in Planar Graphs
Heike Ripphausen-Lipa, Dorothea Wagner, Karsten Weihe · SIAM Journal on Computing · 1997
We consider the problem of finding a maximum collection of vertex-disjoint paths in undirected, planar graphs from a vertex s to a vertex t. This problem is usually solved using flow techniques, which lead to ${\cal O}(nk)$ and ${\cal O}(n\sqrt{n})$ running times, respectively, where n is the number of vertices and k the maximum number of vertex-disjoint $(s,t)$-paths. The best previously known algorithm is based on a divide-and-conquer approach and has running time ${\cal O}(n\log n)$. The approach presented here is completely different from these methods and yields a linear-time algorithm.