We describe algorithms to efficiently compute minimum (
s,
t)-cuts and global mini- mum cuts of undirected surface-embedded graphs. Given an edge-weighted undirected graph
G with
n vertices embedded on an orientable surface of genus g, our algorithms can solve either problem in
gO(g)n log log
n or 2
O(g)n log
n time, whichever is better. When
g is a constant, our
gO(g)n log log
n time algorithms match the best running times known for computing minimum cuts in planar graphs. Our algorithms for minimum cuts rely on reductions to the problem of finding a minimum-weight subgraph in a given
Z2-homology class, and we give efficient algorithms for this latter problem as well. If
G is embedded on a surface with genus
g and
b boundary components, these algorithms run in (
g+
b)
O(g+b) log log
n and 2
O(g+b)n log
n time. We also prove that finding a minimum-weight subgraph homologous to a single input cycle is NP-hard, showing that it is likely impossible to improve upon the exponential dependencies on
g for this latter problem.
This is a combined full version of three conference papers: