Datensatz

Zusammenfassung

$n$-vertex graph of positive genus $g$ and maximal degree $k$ has an $O(\sqrt{gkn})$ edge separator. This bound is best possible to within a constant factor. The separator can be found in $O(g+n)$ time provided that we start with an imbedding of the graph in its genus surface. This extends known results on planar graphs and similar results about vertex separators. We apply the edge separator to the isoperimetric problem, to efficient embeddings of graphs of genus $g$ into various classes of graphs including trees, meshes and hypercubes and to showing lower bounds on crossing numbers of $K_n,K_{m,n}$ and $Q_n$ drawn on surfaces of genus $g$.