How to find a maximum flow in a planar graph?

1.7k views Asked by At

I know an algo to find the minimum cut in a planar graph.

Works as O(NlogN)

You create a dual graph where each vertice corresponds to original's graph facet and edge corresponds to a minimum edge connecting two facets.

Then you use Dijkstra to find the minimum path in this graph.

This way it is possible to find a minimum cut and count the flow value.

But how can I find any of the sets of the original graph edges which provide this flow value?

1

There are 1 answers

0
Shay Mozes On

The algorithm you are sort of describing only works for undirected graphs (Reif's algorithm). Hassin and Johnson showed how to ectend it to compute the max flow. Recently it was shown that these algorithms can be implemented in O(n loglog n) time. See G. F. Italiano, Y. Nussbaum, P. Sankowski, and C. Wulff-Nilsen Improved Algorithms for Min Cut and Max Flow in Undirected Planar Graphs. in Proc. 43rd ACM Symposium on Theory of Computing (STOC), San Jose, 2011.

in directed planar graphs the fastest known algorithm runs in O(n log n) see http://web.engr.oregonstate.edu/~glencora/papers/other/Borradaile08-thesis-dissertation.pdf or http://compgeom.cs.uiuc.edu/~jeffe/pubs/parshort.html