Multicommodity Flows in Planar Undirected Graphs and Shortest Paths

This paper deals with the multicommodity flow problems for two classes of planar undirected graphs. The first class C 12 consists of graphs in which each source-sink pair is located on one of two specified face boundaries. The second class C 01 consists of graphs in which some of the source-sink pairs are located on a specified face boundary and all the other pairs share a common sink located on the boundary. We show that the multicommodity flow problem for a graph in C 12 (resp. C 01 ) can be reduced to the shortest path problem for an undirected (resp. a directed) graph obtained from the dual of the original undirected graph.

Authors

• Hitoshi Suzuki
• Takao Nishizeki
• Nobuji Saito

Keywords

No keywords are indexed for this paper.