Paths and metrics in a planar graph with three or more holes. II: Paths (Q1322004)

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 \(s_ 1,\dots,s_ r\), \(t_ 1,\dots,t_ r\) are vertices of \(G\) such that each pair \(\{s_ i,t_ i\}\) belongs to the boundary of some of \(I\), \(J\), \(K\), and that the graph \((VG,EG\cup\{\{s_ 1,t_ 1\},\dots,\{s_ r,t_ r\}\})\) is Eulerian. We prove that there exist edge-disjoint paths \(P_ 1,\dots,P_ r\) in \(G\) such that each \(P_ i\) connects \(s_ i\) and \(t_ i\) 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) multicommodity 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 (see the foregoing review). We also exhibit an instance with four holes for which the multicommodity flow problem is solvable but required paths do not exist.