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. (epubs.siam.org)

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.