We study the quantitative geometry of graphs in terms of their genus, using the structure of certain "cut graphs," i.e. subgraphs whose removal leaves a planar graph. In particular, we give optimal bounds for random partitioning schemes, as well as various types of embeddings. Using these geometric primitives, we present exponentially improved dependence on genus for a number of problems like approximate max-flow/mincut theorems, approximations for uniform and nonuniform Sparsest Cut, treewidth approximation, Laplacian eigenvalue bounds, and Lipschitz extension theorems and related metric labeling problems. We list here a sample of these improvements. All the following statements refer to graphs of genus g, unless otherwise noted. • 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 general demands, we show that the worst possible gap is O(log g + C P ), where C P is the gap for planar graphs. This dependence is optimal, and already yields a bound of O(log g + √ log n), improving over the previous bound of O( • We give an O( √ log g)-approximation for the uniform Sparsest Cut, balanced vertex separator, and treewidth problems, improving over the previous • If a graph G has genus g and maximum degree D, we show that the kth Laplacian eigenvalue of G is (log g) • We show that if (X, d) is the shortest-path metric on a graph of genus g and S ⊆ X, then every This improves over the previous bound of O (Lg) [LN05], and compares to a lower bound of Ω(L √ 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 every n-vertex shortest-path metric on a graph of genus g embeds into L 2 with distortion O(log g + √ log n), improving over the previous bound of O( √ g log n). Our result is asymptotically optimal for every dependence g = g(n).
The ideas developed in this line of work lead to an asymptotically optimal padding parameter of O(log g) for genus-g graphs REF .
Genus and the geometry of the cut graph
SODA '10
Mathematics Computer Science