Congestion in planar graphs with demands on faces

الأصل · EN

We give an algorithm to route a multicommodity flow in a planar graph G with congestion O(k), where k is the maximum number of terminals on the boundary of a face, when each demand edge lie on a face of G. We also show that our specific method cannot achieve a substantially better congestion.