Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus
Viresh S. Patel · SIAM Journal on Computing · 2013
In this paper, we give the first polynomial-time algorithm for determining the edge expansion for a graph of fixed orientable genus. We show that for a multigraph $G$ with $m$ edges and orientable genus $g$, the edge expansion of $G$ can be determined in time $m^{O(g)}$. We show that the same is true for various other similar measures of edge connectivity.