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.