a Faculty of Commerce and Business Administration, The University of British Columbia, Vancouver, BC, Canada V6T 1Z2
b Faculty of Industrial Engineering and Management, Technion-Israel Institute of Technology, Haifa, Israel 32000
Abstract:
In this paper we study the maximum two-flow problem in vertex- and edge-capacitated undirected ST2-planar graphs, that is, planar graphs where the vertices of each terminal pair are on the same face. For such graphs we provide an O(n) algorithm for finding a minimum two-cut and an O(nlogn) algorithm for determining a maximum two-flow and show that the value of a maximum two-flow equals the value of a minimum two-cut. We further show that the flow obtained is half-integral and provide a characterization of edge and vertex capacitated ST2-planar graphs that guarantees a maximum two-flow that is integral. By a simple variation of our maximum two-flow algorithm we then develop, for ST2-planar graphs with vertex and edge capacities, an O(nlogn) algorithm for determining an integral maximum two-flow of value not less than the value of a maximum two-flow minus one.