A separator theorem for graphs of bounded genus. (English) Zbl 0556.05022

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, 177-189 (1979; Zbl 0432.05022)]. 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.


05C10 Planar graphs; geometric and topological aspects of graph theory
57M15 Relations of low-dimensional topology with graph theory
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity


Zbl 0432.05022
Full Text: DOI Link