Presentation: Monge Property and Max-Flows in Planar Graphs

If you are interested in max-flow computations in planar graphs, below is the talk I have given at WORKER 2013. It gives an overview of how to use shortest paths and Monge property to get the following three results:

  • O(n log log n) time algorithm for undirected max-flow in planar graphs [1], shop
  • almost linear time algorithm for all-source all-sink max-flow in undirected planar graphs, i.e., it computes Gumory-Hu tree [2],
  • almost linear time algorithm for single-source all-sink max-flow in directed planar graphs [3].

[1] Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, Christian Wulff-Nilsen: Improved algorithms for min cut and max flow in undirected planar graphs. STOC 2011: 313-322.
[2] Glencora Borradaile, Piotr Sankowski, Christian Wulff-Nilsen: Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time. FOCS 2010: 601-610.
[3] Jakub Lacki, Yahav Nussbaum, Piotr Sankowski, Christian Wulff-Nilsen: Single Source - All Sinks Max Flows in Planar Digraphs. FOCS 2012: 599-608.

2 thoughts on “Presentation: Monge Property and Max-Flows in Planar Graphs

Leave a Reply

Your email address will not be published. Required fields are marked *