Campus Event Calendar

Event Entry

What and Who

An Approximate Generalization of the Okamura-Seymour Theorem

Nikhil Kumar
Hasso Plattner Institute
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Tuesday, 6 December 2022
60 Minutes
E1 4


Given a graph G with edge capacities and multiple source-sink pairs, each with an associated demand, the multicommodity flow problem is to route all demands simultaneously without violating edge capacities. The problem was first formulated in the context of VLSI routing in the 70’s and since then it has seen a long and impressive line of work. In this work, we consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands. We consider the following generalization of this setting and prove an approximate max flow-min cut theorem: for every demand edge, there exists a face containing both its end points. We show that the cut-condition is sufficient for routing Ω(1)-fraction of all the demands. To prove this, we give a L_1-embedding of the planar metric which approximately preserves distance between all pair of points on the same face.


Roohani Sharma
+49 681 9325 1116
--email hidden

Virtual Meeting Details

passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk online but do not have the password, contact Roohani Sharma at

Roohani Sharma, 11/25/2022 14:31
Roohani Sharma, 11/22/2022 10:09 -- Created document.