Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus

Abstract

In this paper, we show that for an $n$-vertex graph $G$ of genus $g$, the edge expansion of $G$ can be determined in time $n^{O(g^2)}$. We show that the same is true for various other similar measures of edge connectivity.

20 pages

Cited by in corpus (1)

• New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut