On fractional multicommodity flows and distance functions (Q1119950)

The authors establish some results on fractional and integral solutions to multicommodity flow problems. The following is proven. Let \(G=(V,E)\) be a planar bipartite graph. There exist subsets \(W_ 1,W_ 2,...,W_ t\) of V so that for each pair \(v'\), \(v''\) of vertices on the boundary of G, the distance of \(v'\) and \(v''\) in G is equal to the number of \(j=1,...,t\) with \(| \{v',v''\}\cap W_ j| =1\) and so that the cuts \(\delta (W_ j)\) are pairwise disjoint.