Multicommodity flows in graphs

AbstractSuppose that G is a graph, and (si,ti) (1≤i≤k) are pairs of vertices; and that each edge has a integer-valued capacity (≥0), and that qi≥0 (1≤i≤k) are integer-valued demands. When is there a flow for each i, between si and ti and of value qi, such that the total flow through each edge does not exceed its capacity? Ford and Fulkerson solved this when k=1, and Hu when k=2. We solve it for general values of k, when G is planar and can be drawn so that s1,…, sl, t1, …, tl,…,tl are all on the boundary of a face and sl+1, …,Sk, tl+1,…,tk are all on the boundary of the infinite face or when t1=⋯=tl and G is planar and can be drawn so that sl+1,…,sk, t1,…,tk are all on the boundary of the infinite face. This extends a theorem of Okamura and Seymour