Edge-disjoint paths in planar graphs (Q1069956)

The following problem is considered. Given a planar graph G, find k edge- disjoint paths in G connecting k pairs of terminals specified on the outer face of G. A necessary and sufficient condition for the existence of such a collection of paths is given in the case when each node of G not on the outer face has even degree. This generalizes earlier results on \textit{H. Okamura} and \textit{P. D. Seymour} [J. Comb. Theory, Ser. B 31, 75-81 (1981; Zbl 0465.90029)] and the author [Combinatorica 2, 361-371 (1982; Zbl 0515.05044)]. The proof gives rise to a polynomial algorithm for solving the above problem. In particular, the integral multicommodity flow problem belongs to class P when the underlying graph is outerplanar.