A separator theorem for graphs of bounded genus

Reviewer: Abraham Kandel

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. In this paper, the authors claim that if a n vertex graph can be drawn on a surface of genus g, where the genus of a graph is the minimum number of handles that must be added to a sphere so that the graph can be embedded in the resulting surface with no crossing edges, then it can be bisected by removal of 0(sqrt ( gn)) vertices. Applications of this result can be found in layout of circuits in models of VLSI, efficient spare Gaussian elimination, and the solution of various geometric problems.