Premium
On multicommodity flows in planar graphs
Author(s) -
Hassin Refael
Publication year - 1984
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230140204
Subject(s) - counterexample , planar graph , multi commodity flow problem , mathematics , planar , flow (mathematics) , face (sociological concept) , graph , integer (computer science) , flow network , property (philosophy) , discrete mathematics , combinatorics , plane (geometry) , directed graph , undirected graph , mathematical optimization , computer science , social science , philosophy , computer graphics (images) , geometry , epistemology , sociology , programming language
Okamura and Seymour recently proved two properties of multicommodity flows in undirected planar networks where all the sources and the sinks are on a common face of the underlying graph. One is that a feasible solution is guaranteed whenever each cut's capacity is at least as large as the cut's demand. The second is that if all demands and capacities are integers then the flow values may be chosen half‐integer‐valued. In this paper we use the first property to construct two computational procedures; one examines the existence of a feasible flow, and the other constructs such a flow if one exists. We also show that the construction procedure can be used as an alternative proof to the above properties. Finally we show, by presenting counterexamples, that the half‐integrality property does not necessarily hold when either the graph cannot be drawn in the plane with all sources and sinks on a common face, or the graph is directed.