Chapter 53. Graph Separators
Chapter 53. Graph Separators
A graph separator is a set of vertices or edges whose removal divides a graph into smaller pieces.
Separators generalize the ideas of cut vertices, cut sets, and minimum cuts. Instead of merely disconnecting a graph, separators are often required to break the graph into balanced regions. This makes them useful in algorithms, divide-and-conquer methods, sparse matrix computation, geometric graph theory, and network analysis.
The central question is the following:
How small can a set be while still splitting the graph into substantially smaller parts?
This question leads to separator theorems, one of the major themes of structural graph theory.
53.1 Vertex Separators
Let
$$ G=(V,E) $$
be a graph.
A vertex separator is a set
$$ S\subseteq V $$
such that
$$ G-S $$
is disconnected.
Equivalently, removing the vertices in (S) breaks the graph into at least two connected components.
This is the same basic notion used in vertex connectivity.
However, separator theory usually imposes an additional balancing condition. The goal is not merely to disconnect the graph, but to divide it into reasonably small pieces.
53.2 Balanced Separators
Suppose
$$ V=A\cup S\cup B, $$
where the three sets are pairwise disjoint.
The set (S) is called a balanced separator if:
- there are no edges between (A) and (B), and
- both (A) and (B) are substantially smaller than (V).
A common balance condition is
$$ |A|,|B| \le \frac{2}{3}|V|. $$
The constant (2/3) is conventional rather than fundamental. Any constant strictly below (1) gives a meaningful notion of balance.
The idea is that after removing (S), no remaining component is too large.
Balanced separators are useful because they support recursive decomposition. If each recursive step removes only a small separator and reduces the problem size substantially, divide-and-conquer algorithms become efficient.
53.3 Edge Separators
An edge separator is a set of edges whose removal disconnects the graph.
In separator theory, edge separators are often required to satisfy balance conditions analogous to those for vertex separators.
Thus one seeks a partition
$$ V=A\cup B $$
such that:
- both (A) and (B) are reasonably large,
- only a small number of edges run between them.
This is closely related to cuts and expansion.
A graph with poor expansion has small balanced edge separators. A graph with strong expansion resists balanced separation.
53.4 Separators and Expansion
Expansion and separators are dual ideas.
Expansion asks:
How large is the boundary of every set?
Separator theory asks:
Can the graph be split into balanced parts using only a small boundary?
If a graph has strong expansion, then every reasonably large set has many outgoing edges or neighbors. Therefore no small balanced separator exists.
Conversely, if a graph has small balanced separators, then some large regions are only weakly connected to the rest of the graph.
Thus:
| Property | Structural meaning |
|---|---|
| Large expansion | No small balanced separators |
| Small balanced separators | Existence of bottlenecks |
| Expander graph | Hard to partition |
| Planar graph | Often easy to separate |
This contrast is one reason separators are central in graph structure theory.
53.5 The Planar Separator Theorem
The most famous separator theorem concerns planar graphs.
A planar graph is a graph that can be drawn in the plane without edge crossings.
The planar separator theorem states:
Every planar graph on (n) vertices has a balanced vertex separator of size
$$ O(\sqrt{n}). $$
More precisely, there exists a constant (c) such that every planar graph has a separator (S) with
$$ |S|\le c\sqrt{n}, $$
and every component of (G-S) contains at most
$$ \frac{2n}{3} $$
vertices. The theorem was proved by Lipton and Tarjan in 1979 and is one of the foundational results of planar graph algorithms.
This theorem is remarkable because planar graphs may have arbitrarily many vertices, yet a relatively small separator always exists.
53.6 Why the Planar Separator Theorem Matters
The planar separator theorem gives recursive structure.
Suppose a planar graph has (n) vertices. Remove a separator of size (O(\sqrt{n})). The graph breaks into smaller pieces, each containing at most (2n/3) vertices.
Apply the theorem recursively to each piece.
This produces a decomposition tree whose depth is logarithmic in (n). Because the separators are small, many algorithms become faster.
Applications include:
| Area | Benefit |
|---|---|
| Shortest paths | Faster divide-and-conquer algorithms |
| Sparse matrix factorization | Reduced fill-in |
| Dynamic programming | Recursive decomposition |
| Graph drawing | Hierarchical layouts |
| Scientific computing | Domain decomposition |
| Geographic networks | Efficient partitioning |
The theorem explains why planar graphs are algorithmically easier than arbitrary graphs.
53.7 Grid Example
Consider the (m\times m) grid graph.
It contains
$$ n=m^2 $$
vertices.
A vertical line through the grid cuts it into two roughly equal halves. The separator contains approximately
$$ m=\sqrt{n} $$
vertices.
Thus the grid already suggests the planar separator phenomenon:
$$ \text{separator size} \approx \sqrt{n}. $$
The planar separator theorem says that every planar graph behaves similarly, even when its geometry is much more complicated.
53.8 Tree Separators
Trees have especially simple separators.
Every tree has a vertex whose removal leaves components of size at most
$$ \frac{n}{2}. $$
Such a vertex is called a centroid of the tree.
To find one, start at any vertex and repeatedly move into a component containing more than half the vertices. This process eventually stops at a centroid.
Thus trees always have balanced separators of size (1).
This reflects the fact that trees have extremely sparse structure.
53.9 Separators in Minor-Closed Families
The planar separator theorem generalizes to many graph classes.
A graph class is minor-closed if every minor of a graph in the class also belongs to the class.
Examples include:
| Class | Minor-closed? |
|---|---|
| Planar graphs | Yes |
| Forests | Yes |
| Graphs embeddable on a fixed surface | Yes |
| Bipartite graphs | No |
| Regular graphs | No |
Many proper minor-closed families satisfy separator theorems similar to the planar case.
A broad principle is:
Graphs excluding a fixed minor tend to have small separators.
This principle became central in the Robertson-Seymour graph minor theory.
53.10 Spectral Separators
Separators can also be studied through eigenvalues.
The Laplacian matrix of a graph is
$$ L=D-A, $$
where (D) is the degree matrix and (A) is the adjacency matrix.
The second-smallest eigenvalue of (L), often called the algebraic connectivity, measures how difficult it is to separate the graph.
A small second eigenvalue usually indicates the existence of a sparse cut or separator.
This connection appears in spectral partitioning algorithms.
The basic idea is:
- Compute an eigenvector associated with a small eigenvalue.
- Use the eigenvector coordinates to partition the vertices.
- Obtain a separator with relatively small boundary.
This is one of the main links between linear algebra and graph partitioning.
53.11 Separator Hierarchies
Repeated application of separators creates a separator hierarchy.
At the top level, remove a separator and split the graph into smaller regions. Then recursively separate each region.
This produces a decomposition tree.
Separator hierarchies are useful because they allow large graphs to be processed locally. Many algorithms can solve subproblems independently and combine the results through the separator interface.
The efficiency often depends on:
| Quantity | Importance |
|---|---|
| Separator size | Communication between subproblems |
| Balance ratio | Recursion depth |
| Recursive structure | Overall complexity |
Small balanced separators lead to efficient recursive algorithms.
53.12 Treewidth and Separators
Separators are closely related to treewidth.
Informally, treewidth measures how tree-like a graph is.
Graphs with small treewidth admit small separators. Conversely, recursive small-separator structure often implies bounded or moderately bounded treewidth.
For example:
| Graph type | Separator behavior |
|---|---|
| Trees | Separator size (1) |
| Outerplanar graphs | Small separators |
| Planar graphs | Separator size (O(\sqrt{n})) |
| Expanders | No sublinear balanced separators |
Expanders therefore have large treewidth.
This relationship is one reason separator theory is central in structural graph theory and parameterized complexity.
53.13 Vertex Separators Between Two Vertices
A separator may also be local.
For distinct vertices (s) and (t), an (s)-(t) separator is a set
$$ S\subseteq V\setminus{s,t} $$
such that (s) and (t) lie in different connected components of
$$ G-S. $$
Menger's theorem states that the minimum size of such a separator equals the maximum number of internally vertex-disjoint (s)-(t) paths.
Thus local separators and disjoint paths are dual concepts.
53.14 Edge Separators and Conductance
In applications involving random walks and clustering, edge separators are often normalized.
One common quantity is conductance.
For a set (S\subseteq V),
$$ \Phi(S) = \frac{|\partial_E S|} {\min(\operatorname{vol}(S),\operatorname{vol}(V\setminus S))}, $$
where
$$ \operatorname{vol}(S) = \sum_{v\in S}\deg(v). $$
Conductance measures how difficult it is for a random walk to escape from (S).
Small conductance indicates a bottleneck. Large conductance indicates strong mixing.
Conductance is closely related to spectral gaps and Cheeger inequalities.
53.15 Separator Algorithms
Several algorithmic approaches are used to find separators.
| Method | Main idea |
|---|---|
| Breadth-first layering | Use graph distance structure |
| Spectral partitioning | Use Laplacian eigenvectors |
| Flow-based methods | Use minimum cuts |
| Geometric methods | Use embeddings and coordinates |
| Recursive decomposition | Build separator hierarchies |
For planar graphs, linear-time separator algorithms are known.
For general graphs, finding optimal balanced separators is usually computationally difficult.
53.16 Applications
Separators appear throughout theoretical and applied graph theory.
| Area | Role of separators |
|---|---|
| Divide-and-conquer algorithms | Split problems recursively |
| Sparse linear systems | Reduce fill-in during elimination |
| Scientific computing | Domain decomposition |
| Parallel computing | Minimize communication |
| Graph clustering | Detect communities |
| VLSI design | Partition circuits |
| Geographic information systems | Decompose road networks |
| Machine learning | Partition similarity graphs |
The basic idea is always the same:
Break a large graph into manageable pieces while minimizing interaction between pieces.
53.17 Expanders as Separator-Resistant Graphs
Expander graphs behave oppositely from planar graphs.
A planar graph has small balanced separators:
$$ O(\sqrt{n}). $$
A bounded-degree expander has no small balanced separators. Any balanced separator must contain linearly many vertices or edges.
Thus expanders are difficult to partition.
This contrast is fundamental:
| Graph family | Separator behavior |
|---|---|
| Trees | Constant-size separators |
| Planar graphs | (O(\sqrt{n}))-size separators |
| Minor-closed families | Often sublinear separators |
| Expanders | Linear-size separators |
Separator size therefore reflects global structure.
53.18 Common Mistakes
A common mistake is to think that every separator must disconnect the graph into exactly two components. In general, removing a separator may create many components.
Another mistake is to ignore balance. A separator isolating one vertex may be small but not useful for divide-and-conquer algorithms.
A third mistake is to confuse connectivity with separator size. A graph may have large minimum degree but still admit relatively small balanced separators.
A fourth mistake is to assume that separators always correspond to geometric cuts. Spectral and combinatorial separators may not have obvious geometric interpretations.
53.19 Summary
Graph separators divide graphs into smaller pieces by removing relatively few vertices or edges.
| Concept | Meaning |
|---|---|
| Vertex separator | Vertex set whose removal disconnects the graph |
| Edge separator | Edge set whose removal disconnects the graph |
| Balanced separator | Separator leaving no very large component |
| Planar separator theorem | Planar graphs have (O(\sqrt{n}))-size balanced separators |
| Separator hierarchy | Recursive decomposition using separators |
| Spectral separator | Separator found through eigenvalues |
| Conductance | Normalized edge boundary measure |
Separator theory studies how global graph structure can be decomposed. It connects connectivity, expansion, spectral methods, recursive algorithms, and structural graph theory.