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

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

J. Algorithms 5, 391-407 (1984).

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.

MSC:

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

Keywords:

graph algorithms; separators in graphs; graph bisection; planar graphs

Citations:

Zbl 0432.05022