Paths and metrics in a planar graph with three or more holes. II: Paths (Q1322004)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Paths and metrics in a planar graph with three or more holes. II: Paths |
scientific article |
Statements
Paths and metrics in a planar graph with three or more holes. II: Paths (English)
0 references
6 June 1994
0 references
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.
0 references
holes
0 references
planar graph
0 references
Euclidean plane
0 references
edge-disjoint paths
0 references
multicommodity flow
0 references
packing
0 references