#
Global Minimum Cuts in Surface Embedded Graphs

## Presenter: Lowell Trott

## Jeff Erickson, Kyle Fo, Amir Nayyeri

The authors give a deterministic algorithm to find the minimum cut in a surface-embedded graph in near-linear time. Given an undirected graph embedded on an orientable surface of genus g, our algorithm computes the minimum cut in g^{O(g)}*nloglogn time, matching the running time of the fastest algorithm known for planar graphs, due to .a .cki and Sankowski, for any constant g.