A separator theorem for graphs of bounded genus

John R. Gilbert, Joan P. Hutchinson, Robert Endre Tarjan

Research output: Contribution to journalArticlepeer-review

189 Scopus citations


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 an n-vertex graph can be drawn on the plane, then it can be bisected by removal of O(sqrt(n)) vertices (R. J. Lipton and R. E. Tarjan, SIAM J. Appl. Math.36 (1979), 177-189). The main result of the paper is that if a graph can be drawn on a surface of genus g, then it can be bisected by removal of O(sqrt(gn)) vertices. This bound is best possible to within a constant factor. An algorithm is given 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. Some extensions and applications of these results are discussed.

Original languageEnglish (US)
Pages (from-to)391-407
Number of pages17
JournalJournal of Algorithms
Issue number3
StatePublished - Sep 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'A separator theorem for graphs of bounded genus'. Together they form a unique fingerprint.

Cite this