A Separator Theorem for Graphs of Bounded Genus

Many divide-and-conquer algorithms on graphs are based on finding a small set of vertices or edges whose removal divides the graph roughly in half. Most graphs do not have the necessary small separators, but some useful classes do. One such class is planar graphs: If we can draw an n-vertex graph on the plane, then we can bisect it by removing $O(\sqrt{n})$ vertices [Lipt79b]. The main result of this paper is that if we can draw a graph on a surface of genus g, then we can bisect it by removing $O(\sqrt{gn})$ vertices. This bound is best possible to within a constant factor. We give an algorithm for finding the separator that takes time linear in the number of edges in the graph, given an embedding of the graph in its genus surface. We discuss some extensions and applications of these results