Algorithms for multicommodity flows in planar graphs

This paper gives efficient algorithms for the muiticommodity flow problem for two classes C₁₂ and C₀₁ of planar undirected graphs. Every graph in C₁₂ has two face boundaries B₁ and B₂ such that each of the source-sink pairs lies on B₁ or B₂. On the other hand, every graph inC₀₁ has a face boundaryB₁ such that some of the source-sink pairs lie onB₁ and all the other pairs share a common sink lying onB₁. The algorithms run inO(kn +nT(n)) time if a graph hasn vertices andk source-sink pairs andT(n) is the time required for finding the single-source shortest paths in a planar graph ofn vertices.