The few points that cut a flat graph

Two graphs that will not lie flat decides which graphs can be drawn without crossings, and five spokes squeezed into K5 shows the decision can be phrased by forbidding what a graph contains. Neither says what being planar buys.

The most useful answer is about cutting. Take a graph with $n$ points and remove a set $S$ of them, the separator, so that what is left falls into pieces with no edges between them, none holding more than two thirds of the $n$ points. For an arbitrary graph $S$ may need to be a constant fraction of everything. Richard Lipton and Robert Tarjan proved in 1979 that for a planar graph it never does:

$$|S| \le 2\sqrt2\,\sqrt n \approx 2.83\sqrt n.$$

A planar graph with a million points can be split into two parts of at most two thirds by removing fewer than three thousand of them, and the split can be found in time proportional to $n$. Flatness is a statement about crossings; the separator theorem turns it into a statement about bottlenecks, and bottlenecks are what divide-and-conquer algorithms need.

Why the square root cannot be beaten #

Before the upper bound, the lower one: some planar graphs genuinely need about $\sqrt n$ points.

The $k \times k$ grid has $n = k^2$ points and is planar. Remove a set $S$ with fewer than $k/3$ points. They lie in fewer than $k/3$ rows and fewer than $k/3$ columns, so at least $2k/3$ rows are untouched and at least one column is. An untouched row is a connected path of $k$ points; it crosses the untouched column; so every untouched row is in the same piece as that column. That piece holds at least $(2k/3) \cdot k = 2n/3$ points — and strictly more once the column’s own points in the touched rows are counted.

So no set of fewer than $k/3 = \sqrt n / 3$ points separates the grid. The removal drawn uses three points on a twelve-by-twelve grid, just under the threshold of four, and the piece that survives is nearly everything. The middle column, with $k$ points, does separate it. The truth for the grid lies between $\sqrt n / 3$ and $\sqrt n$, and the separator theorem’s $2.83\sqrt n$ is within a constant factor of what the grid forces.

The argument is purely about rows and columns, and it generalises only in spirit. What the grid has is that every short cut leaves a long connected cross intact. A planar graph with long thin parts — a path, a tree — can be cut by a single point; the grid is hard because it is fat in every direction, and the square root is the width of a fat planar graph.

Rings of equal distance #

The upper bound starts from breadth-first search. Pick a point near the middle of the graph, and sort all points by how many edges they are from it.

The triangulation is the Delaunay one: each triangle’s circumscribed circle contains no other point. It is planar by construction, has close to the maximum $3n - 6$ edges, and looks like the planar graphs that arise from meshes and maps. It also carries the shortest network joining the points among its edges, which is one reason it is the standard mesh: whatever a computation needs from near neighbours is already in it.

The set of points at one fixed distance — a level — is always a separator of a kind. An edge joins points whose distances differ by at most one, so nothing inside a level can reach anything outside it without passing through it. The question is only whether a level is both thin and balanced: few points on it, and at most two thirds of the graph on each side.

The balanced levels are the ones near the middle of the sequence, and there is a counting reason one of them is thin when the levels are numerous: their sizes add up to $n$, so if there are many levels in the balanced range, the smallest cannot be large. If the balanced range is short instead, the whole graph is shallow — every point close to the centre — and a different kind of cut is available.

Levels are useful even when they are not thin. Brenda Baker showed in 1994 that deleting every $k$-th level — all points at distances $j, j + k, j + 2k, \dots$ for one offset $j$ — leaves a planar graph made of bands only $k$ levels deep, on which many hard problems can be solved exactly by dynamic programming. The $k$ possible offsets delete disjoint sets of points, so for at least one of them the deleted points hold at most a $1/k$ share of an optimal solution. Choosing $k$ large gives a solution within any fixed factor of the best for problems such as the largest set of points with no two joined, which on general graphs cannot be approximated within any constant factor unless P = NP. The levels are the same rings the figure draws; the argument uses many of them at once instead of one.

A cycle through a shallow tree #

The second ingredient handles exactly that shallow case, and it uses planarity in a way the levels do not.

Keep the breadth-first tree: each point joined to one neighbour a step closer to the centre. In a triangulation, every edge not in the tree closes a fundamental cycle — the edge itself plus the two tree paths from its ends back to where they meet. If the tree has depth $d$, that cycle has at most $2d + 1$ points. Because the graph is drawn flat, the cycle is a closed curve, and it divides the remaining points into those inside and those outside.

Some fundamental cycle always leaves at most two thirds on each side in a triangulation. The argument walks from cycle to cycle. Start from any non-tree edge; if too much is inside, look at the triangle on the inner side of that edge. Its third corner lies inside or on the cycle, and replacing the edge by one of the triangle’s other edges gives a new fundamental cycle enclosing strictly fewer points. Repeat until the inside is at most two thirds. The step cannot overshoot badly: when the third corner is strictly inside, the old inside is split between two smaller cycles through that corner, and taking the one with more inside keeps at least half of what was there — so an inside of more than two thirds becomes one of roughly a third or more, which leaves at most two thirds outside as well.

That is where flatness enters. A cycle separates the plane, so its inside and outside are disconnected once it is removed. On a torus a cycle need not separate anything, and graphs on surfaces of genus $g$ have separators of size about $\sqrt{gn}$ instead — larger, but still sublinear.

Levels and cycles, combined #

Lipton and Tarjan’s proof uses both pieces.

Let $\ell_1$ be the level containing the median point by distance. Search downwards from $\ell_1$ for a level $\ell_0$ whose size, plus twice its distance to $\ell_1$, is at most about $2\sqrt n$, and upwards for a level $\ell_2$ with the same property. Such levels exist by the counting argument: if every level within $\sqrt n$ steps were larger than that, those levels alone would hold more than $n$ points.

Removing $\ell_0$ and $\ell_2$ cuts the graph into three bands. The outer two are already small enough, being on the far sides of the median. The middle band may be too large, but it is at most about $\sqrt n$ levels thick. Contract everything inside $\ell_0$ to a single point, triangulate the band, and its breadth-first tree from that point has depth under $\sqrt n$ — so a fundamental cycle of fewer than $2\sqrt n$ points splits the band into parts of at most two thirds. The two levels and the cycle together form the separator, and the bookkeeping of the constants gives $2\sqrt2\sqrt n$.

In random triangulations like these, a single well-chosen level already does almost all the work: its size tracks $2.32\sqrt n$ across a 32-fold range. That is not the theorem — a level can be badly unbalanced, or thick, on a graph designed to defeat it — but it shows what the theorem is about. Doubling the graph multiplies the cut by about 1.41, not by 2.

The theorem’s guarantee is looser than what these graphs deliver. For the 160-point triangulation above, $2\sqrt2\sqrt{160} \approx 35.8$, and a single level of 23 points already did better; for the 120-point one the bound is 31, and one cycle of 13 points sufficed. The slack is the price of a statement that must also hold for the worst planar graph with that many points, where a level might be twice as thick as its neighbours and the cycle must be found inside a band rather than across the whole graph. A guarantee and a typical case are different measurements, and the sweep is the second.

The recursion a small cut pays for #

The reason anyone wants a separator is recursion. Cut the graph, solve the problem on each piece, and combine the answers across the cut; if the cut is small, combining is cheap, and each piece is again planar and can be cut again.

This recursion is nested dissection, introduced by Alan George in 1973 for grids and extended to all planar graphs by Lipton, Donald Rose and Tarjan in 1979. Its first use was solving the sparse linear systems that come from meshes. Gaussian elimination on such a system creates new non-zero entries, called fill, and the order in which unknowns are eliminated decides how much. Eliminating the pieces first and the separators last confines the fill: on a $k \times k$ grid, ordering the unknowns row by row produces fill of order $n^{3/2}$ and work of order $n^2$, while nested dissection produces fill of order $n \log n$ and work of order $n^{3/2}$. For a mesh with a million unknowns that is the difference between $10^{12}$ operations and $10^9$.

The $n^{3/2}$ comes straight from the separator size. The last unknowns eliminated are the top-level cut, about $\sqrt n$ of them, and they end up coupled to one another densely, so eliminating them costs about $(\sqrt n)^3 = n^{3/2}$ operations. The two halves below cost the same in their own terms, $2 \cdot (n/2)^{3/2}$, and summing down the recursion gives a geometric series dominated by its first term. The whole solve costs what its largest cut costs, which is why the constant in front of $\sqrt n$ matters to the people who write these solvers in a way it does not to anyone else.

The same recursion runs underneath much of planar graph algorithmics: shortest paths in time linear in $n$ (Henzinger, Klein, Rao and Subramanian, 1997), approximation schemes for problems that are hard on general graphs, and compact routing tables. In each case the separator is where information has to cross between pieces, and $\sqrt n$ is small enough that crossing it is cheap.

Circles that cut a graph #

There is a second proof of the separator theorem, and it goes through geometry that seems to have nothing to do with graphs.

Every flat graph is a pile of circles: Koebe’s theorem gives every planar graph a drawing in which each point is a disc and two discs touch exactly when their points are joined. Gary Miller, Shang-Hua Teng, William Thurston and Stephen Vavasis used it in 1997. Lift the discs onto a sphere by stereographic projection, move them by a Möbius transformation so that their centres balance around the sphere’s centre, and cut the sphere with a random great circle. Every disc the great circle meets is a separator point, and a disc of radius $r$ is met with probability proportional to $r$. Because the discs do not overlap, their total area is at most the sphere’s, and by the Cauchy–Schwarz inequality the sum of their radii is at most a constant times $\sqrt n$.

So the expected number of discs cut is of order $\sqrt n$, and the balancing of the centres makes each side hold at most a constant fraction. The square root arrives as the ratio between a total area and a total perimeter — the same place it arrives in the grid.

What sample triangulations cannot show #

The sweep measures one heuristic on one kind of graph. Random Delaunay triangulations are round, evenly spread and have no long thin parts; on them a single breadth-first level behaves well. The theorem’s content is that every planar graph admits a small separator, including graphs built to make levels thick or unbalanced, and nothing about the sweep tests that.

The best cycle is found by trying every edge. The figure’s cycle is the most balanced among all fundamental cycles of one tree, and it happens to be well within the two-thirds bound. The theorem’s walking argument finds some such cycle in linear time; the picture does not show the walk.

The pictures do not show optimality. The grid argument gives $\sqrt n / 3$ as a floor and the middle column gives $\sqrt n$ as a ceiling for that graph, but the smallest balanced separator of a random triangulation is not computed anywhere here — finding a minimum balanced separator is hard in general, and every number drawn is a cut that was found, not the smallest that exists.

And the triangulations are drawn with their coordinates. A separator is a combinatorial object and needs no drawing, but the fundamental cycle’s inside and outside are read here from the polygon it forms. For a planar graph given only as a list of edges, the same division comes from an embedding computed by a planarity test, which the drawings take for granted.

Still open: the best constant, and what lies beyond the plane #

The separator theorem is tight up to a constant, and the constant is not known.

Lipton and Tarjan’s $2\sqrt2 \approx 2.83$ was improved to $\sqrt6 \approx 2.45$ by Hristo Djidjev in 1982, and later refinements have pushed it below $2$. The grid and similar constructions give lower bounds of order $\sqrt n$ with smaller constants, and the exact constant for splitting planar graphs into parts of at most two thirds remains undetermined. It matters less than it sounds for algorithms, and it is the kind of number that measures how well the geometry of the plane is understood.

The theorem also extends, and the extension connects back to minors. Noga Alon, Paul Seymour and Robin Thomas proved in 1990 that any graph with no $K_h$ minor has a separator of size at most about $h^{3/2}\sqrt n$ — so the square root is a property of every minor-closed family, not of the plane specifically. Graphs without that structure need not have small separators: random graphs in which every point has three neighbours need a constant fraction of all their points. They are expanders — every set of up to half the points has many edges leaving it — like the Cayley graphs whose diameter is only logarithmic, and expansion is the same property that makes cuts and flows disagree on general networks. Which families do have them was answered by Zdeněk Dvořák and Sergey Norin in 2016, and the answer is phrased in minors again: a family closed under subgraphs has separators of size $n^{1-\varepsilon}$ exactly when its shallow minors — those whose clumps have small radius — have edge density growing at most polynomially in that radius. Minors decide planarity, bound separators and characterise which families have them, three results from one way of letting a graph hide inside another.

A bottleneck measured as a square root #

The idea worth keeping is that a topological condition can be converted into a quantitative bottleneck, and that the bottleneck has a specific size.

Planarity says nothing about size or shape; it says only that edges do not cross. The separator theorem extracts from it a number — a square root — and that number is exactly what grids, meshes and maps have in common: a width that grows as the square root of the area. Euler’s formula gave planar graphs few edges. The separator theorem gives them narrow waists, and narrow waists are what make a large problem into two smaller ones with a cheap seam between them.