TY - JOUR

T1 - A separator theorem for graphs of bounded genus

AU - Gilbert, John R.

AU - Hutchinson, Joan P.

AU - Tarjan, Robert Endre

N1 - Funding Information:
*The work of this author was supported in part by National Science Foundation Grant MCS82-02948.
Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.

PY - 1984/9

Y1 - 1984/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0001345696&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0001345696&partnerID=8YFLogxK

U2 - 10.1016/0196-6774(84)90019-1

DO - 10.1016/0196-6774(84)90019-1

M3 - Article

AN - SCOPUS:0001345696

VL - 5

SP - 391

EP - 407

JO - Journal of Algorithms

JF - Journal of Algorithms

SN - 0196-6774

IS - 3

ER -