Abstract

Flows and cuts were originally developed as tools for studying railway and other transportation networks, which are naturally modeled as planar graphs; Ford and Fulkerson's seminal paper includes an algorithm for planar networks where the source and target vertices lie on the same face. A long series of results has led to planar maximum-flow algorithms that run in $O(n\log n)$ time, first for undirected graphs and more recently for directed graphs. Despite more than half a century of attention on flows in planar graphs, surprisingly little was known about flows in these more general graph families until very recently. Chambers, Erickson and Nayyeri [STOC'09] describe the first near-linear time algorithms for surface embedded graphs. Specially, given an embedded graph on a surface of genus $g$, with two specified vertices $s$ and $t$, they compute the maximum flow in $g^{O(g)}n^{3/2}$ running time. For a graph with integer edge capacities that sum to $C$, they compute the maximum flow in $O(g^7 n \log^2 n \log^2 C)$. Recently, Erickson and Nayyeri [SODA'11] found an $O(2^{O(g)} n \log n)$ algorithm to compute the minimum cut for undirected graphs. This talk will discuss these two papers.



Information: