Paths and metrics in a planar graph with three or more holes. I: Metrics (Q1322003)

Let \(G= (VG,EG)\) be a bipartite planar graph embedded in the Euclidean plane and \(\mathcal H\) be a subset of its faces (holes). A. Schrijver proved that if \(|{\mathcal H}|=2\) then there exist a collection \({\mathcal C}= \{m_ 1,\dots,m_ k\}\) of cut metrics on \(VG\) such that: (i) \(m_ 1(e)+\cdots+ m_ k(e)\leq 1\) for any \(e\in EG\); and (ii) for any vertices \(s\) and \(t\) in the boundary of a hole, the value \(m_ 1(s,t)+\cdots +m_ k(s,t)\) is equal to the distance between \(s\) and \(t\). This is, in general, not true for \(|{\mathcal H}|=3\). In the present paper we prove that: \((*)\) for \(|{\mathcal H}|=3\), (i)-(ii) hold for some \(\mathcal C\) consisting of cut metrics and 2,3-metrics (metrics induced by the graph \(K_{2,3}\)); and \((**)\) for \(|{\mathcal H}|=4\), (i)-(ii) hold for some \(\mathcal C\) consisting of metrics induced by planar graphs with at most four faces.