We study the quantitative geometry of graphs with small genus. In particular, we exhibit new, optimal random partitioning schemes for such graphs. Using these geometric primitives, we give exponentially improved dependence on genus for a number of problems like approximate max-flow/min-cut theorems, approximations for uniform and non-uniform Sparsest Cut, treewidth approximation, Laplacian eigenvalue bounds, Lipschitz extension theorems, and various embeddings into normed spaces.

We list here a sample of these improvements. All the following statements refer to graphs of genus g.

• We show that such graphs admit an O(log g)-approximate multi-commodity max-flow/min-cut theorem for the case of uniform demands. This bound is optimal, and improves over the previous bound of O(g) [KPR93,FT03]. For non-uniform demands, we give a bound of O(sqrt(log g)(log n)), improving over the previous bound of O(sqrt(g log n)) [KLMN04].
• We give an O(log g)-approximation for treewidth, improving over the previous bound of O(g) [FHL05].
• If a graph G has genus g and maximum degree D, the k-th Laplacian eigenvalue of G is (log g)2 * O(k g D/n), improving over the previous bound of g2 * O(k g D/n) [KLPT]. There is a lower bound of Omega(kgD/n), making this result almost tight.
• We show that if (X,d) is the shortest-path metric on a graph of genus g and S is a subset of X, then every L-Lipschitz map f : S -> Z into a Banach space Z admits an O(L log g)-Lipschitz extension f' : X -> Z. This improves over the previous bound of O(Lg) [LN05], and compares to a lower bound of Omega(L sqrt(log g)). In a related way, we show that there is an O(log g)-approximation for the 0-extension problem on such graphs, improving over the previous O(g) bound.
• We show that if planar graphs embed into L_1 with O(1) distortion, then graphs of genus g embed into L_1 with O(log g) distortion, improving over the previous conditional bound of O(g2) [BLS09]. This is conditionally tight, as there is an Omega(log g) lower bound. We also show that every n-vertex shortest-path metric on a graph of genus g embeds into L_2 with distortion O(sqrt((log g)(log n))), improving over the previous bound of O(sqrt(g log n)).

Joint work with James R. Lee.