Distances and cuts in planar graphs

Distances and cuts in planar graphs

0.00 Avg rating0 Votes
Article ID: iaor19881170
Country: United States
Volume: 46
Issue: 1
Start Page Number: 46
End Page Number: 57
Publication Date: Feb 1989
Journal: Journal of Combinatorial Theory Series B
Authors:
Keywords: combinatorial analysis
Abstract:

The paper proves the following theorem. Let G=(V,E) be a planar bipartite graph, embedded in the Euclidean plane. Let O and I be two of its faces. Then there exist pairwise edge-disjoint cuts C1,...,Ct so that for each two vertices v, w with v,wO or v,wI, the distance from v to w in G is equal to the number of cuts Ct separating v and w. This theorem is dual to a theorem of Okamura on plane multicommodity flows, in the same way as a theorem of Karzanov is dual to one of Lomonsov.

Reviews

Required fields are marked *. Your email address will not be published.