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 C12 consists of graphs in which each source-sink pair is located on one of two specified face boundaries. The second class C01 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 C12 (resp. C01) can be reduced to the shortest path problem for an undirected (resp. a directed) graph obtained from the dual of the original undirected graph.