A separator theorem for graphs of bounded genus

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

Research output: Contribution to journalArticle

160 Scopus citations

Abstract

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
Volume5
Issue number3
DOIs
StatePublished - Sep 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

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

  • Cite this