Paths and Metrics in a Planar Graph with Three or More Holes. II. Paths

Suppose that G (VG, EG) is a planar graph embedded in the euclidean plane, that I, J, K are three of its faces (holes), that s1,..., sr, t1,..., tr are vertices of G such that each pair {si, ti} belongs to the boundary of some of I, J, K, and that the graph (VG, EG ∪ { {s1, t1 }, ..., {sr, tr} }) is eulerian. We prove that there exist edge-disjoint paths P1,..., Pr in G such that each Pi connects si and ti, if the obvious necessary conditions with respect to the cuts and the so-called 2, 3-metrics are satisfied. In particular, such paths exist if the corresponding (fractional) multi-commodity flow problem has a solution. This extends Okamura′s theorem on paths in a planar graph with two holes. The proof uses a theorem on a packing of cuts and 2, 3-metrics obtained in Part I of the present series of two papers. We also exhibit an instance with four holes for which the multicommodity flow problem is solvable but the required paths do not exist.