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 -