Edge-disjoint homotopic paths in a planar graph with one hole (Q1097900)

We prove the following theorem, conjectured by K. Mehlhorn: Let \(G=(V,E)\) be a planar graph, embedded in \({\mathbb{R}}^ 2\). Let 0 denote the interior of the unbounded face. Let I be the interior of some fixed bounded face. Let \(C_ 1,...,C_ k\) be curves in \({\mathbb{R}}^ 2\setminus (I\cup 0)\), with end points in \(V\cap \delta (I\cup 0)\), so that for each vertex v of G the degree of v in G has the same parity (mod 2) as the number of curves \(C_ i\) beginning or ending in v (counting a curve beginning and ending in v for two). Then there exist pairwise edge-disjoint paths \(P_ 1,...,P_ k\) in G so that \(P_ i\) is homotopic to \(C_ i\) in the space \({\mathbb{R}}^ 2\setminus (I\cup 0)\) for \(i=1,...,k\), if and only if for each dual path Q from \(I\cup 0\) to \(I\cup 0\) the number of edges in Q is not smaller than the number of times Q necessarily intersects the curves \(C_ i.\) The theorem generalizes a theorem of Okamura and Seymour. Its proof yields a polynomial-time algorithm finding the paths as required.