## Abstract

We describe the first algorithm to compute maximum flows in surface-embedded graphs in near-linear time. Specifically, given a graph embedded on a surface of genus g, with two specified vertices s and t and integer edge capacities that sum to C, our algorithm computes a maximum (s, _{3}^{t})_{2}-flow in O(g^{8}n log^{2}n log^{2} C) time. We also present a combinatorial algorithm that takes g^{O(g)}n^{3/2} arithmetic operations. Except for the special case of planar graphs, for which an O(nlogn)-time algorithm has been known for 20 years, the best previous time bounds for maximum flows in surface-embedded graphs follow from algorithms for general sparse graphs. For graphs of any fixed genus, our algorithms improve these time bounds by roughly a factor of √n. Our key insight is to optimize the homology class of the flow, rather than directly optimizing the flow itself; two flows are in the same homology class if their difference is a weighted sum of directed facial cycles. A dual formulation of our algorithm computes the minimum-cost circulation in a given (real or integer) homology class.

Original language | English (US) |
---|---|

Pages (from-to) | 1605-1634 |

Number of pages | 30 |

Journal | SIAM Journal on Computing |

Volume | 41 |

Issue number | 6 |

DOIs | |

State | Published - 2012 |

## Keywords

- Homology
- Maximum flow
- Topological graph theory

## ASJC Scopus subject areas

- Computer Science(all)
- Mathematics(all)