Algorithms for multicommodity flows in planar graphs (Q1119160)

This paper gives efficient algorithms for two classes \(C_{12}\) and \(C_{01}\) of planar undirected graphs. Every graph in \(C_{12}\) has two face boundaries \(B_ 1\) and \(B_ 2\) such that each of the source-sink pairs lies on \(B_ 1\) or \(B_ 2\). On the other hand, every graph in \(C_{01}\) has a face boundary \(B_ 1\) such that some of the source-sink pairs lie on \(B_ 1\) and all the other pairs share a common sink laying on \(B_ 1\). The algorithms run in \(O(kn+nT(n))\) time if a graph has n vertices and k source-sink pairs and T(n) is the time required for finding the single-source shortest paths in a planar graph of n vertices.