Abstract: We describe the first algorithms to compute maximum flows and minimum cuts in surface-embedded graphs in near-linear time. Given an undirected graph embedded on an orientable surface of genus g, with two specified vertices s and t, our algorithm computes a minimum (s,t)-cut in g^{O(g)} n log n time; if there is time, we will also describe a different algorithm which computes a maximum $(s,t)$-flow in in $O(g7 n \log^2n \log^2C)$ time for integer capacities that sum to $C$, or in $(g \log n)^O(g) n$ time for real capacities. Except for the special case of planar graphs, the best previous time bounds for finding min cuts or max flows in embedded graphs follow from algorithms for general sparse graphs.
This is joint work with Jeff Erickson and Amir Nayyeri, which appeared in SOCG and STOC last year.