Four Shortest Vertex-Disjoint Paths in Planar Graphs

Abstract:
Let G be an edge-weighted planar graph with 2k terminal vertices s₁, t₁, ..., s_k, t_k. The minimum-sum vertex-disjoint paths problem asks for a set of pairwise vertex-disjoint simple paths of minimum total length, where the ith path connects s_i to t_i. Even when all terminals lie on a single face, efficient algorithms for this problem are known only for fixed k≤3. We describe the first polynomial-time algorithm for the case of four arbitrary terminal pairs on a single face.

Four shortest vertex-disjoint paths in planar graphs