Points, spheres, and separators: a unified geometric approach to graph partitioning
Shang‐Hua Teng · 1992
Geometry is full of visual imagination and concrete intuition. Such imagination and intuition is of great value not only for the research worker, but also for anyone who wishes to study and appreciate the results in geometry. In this thesis, a unified geometric approach is presented for graph partitioning--a fundamental problem in computer science that has important applications in numerical analysis, VLSI design, computational geometry, complexity theory, and other fields. The main ingredient in obtaining this unified approach is a novel geometrical characterization of graphs that have small separators, where a separator of a graph is a relatively small subset of vertices whose removal divides the rest of the graph into two disconnected pieces of approximately equal size. The characterization is based on elementary geometric concepts such as points, balls, cubes, and spheres. More specifically, a new class of geometric graphs, overlap graphs, is proposed. This class has the following properties: (1) In two dimensions, planar graphs are special cases of overlap graphs. (2) In d dimensions (d $\ge$ 2), any finite subgraph of the infinite d-dimensional grid is an overlap graph. (3) Every overlap graph of n vertices in d dimensions has an $O(n\sp{(d-1)/d})$ separator. At the time of this writing, this is the first time that a class of graphs has been proposed with these three natural properties. The proof that planar graphs are special cases of overlap graphs relies on recent deep theorems by Andreev and Thurston characterizing all planar graphs in a geometric fashion. A consequence is a new geometric proof of a classical theorem of Lipton and Tarjan that every planar graph has an $O(\sqrt{n})$-separator. This is another beautiful illustration of the use of geometry in understanding combinatorial concepts.