Every point at the average of its neighbours

The crossings a graph cannot avoid counted what a graph costs when it cannot be drawn flat. For the graphs that can — the planar ones — there is a different question, and it is constructive: given a graph known to be planar, produce a drawing without crossings.

Two facts make the question sharper than it looks. István Fáry proved in 1948, as Klaus Wagner had in 1936, that every planar graph can be drawn with straight edges and no crossings — curves are never needed. And planarity can be tested quickly, so the question is not whether a drawing exists but how to find one. A natural guess is that it must be a search: try placements, detect crossings, move points, repeat.

William Tutte showed in 1963 that no search is needed. Fix the points of one face at the corners of a convex polygon. Put every other point at the average of the positions of its neighbours. That is a system of linear equations, it has exactly one solution, and the solution is a drawing.

For the cube, pin one square face to a large square. The four remaining points each have three neighbours — one corner of the big square and two of each other — and the averaging puts them on a smaller square inside, rotated by nothing and centred exactly, because each is pulled equally towards its own corner and its two companions. The result is the familiar picture of a cube seen through one face, and it was not drawn: it was solved for.

Springs, and one solution #

The averaging condition has a physical reading that makes its solution feel inevitable. Replace each edge by a spring of natural length nought and equal stiffness, nail the outer points down, and let the rest go. A free point is in equilibrium when the pulls of its springs cancel, and a spring pulls with force proportional to its length, so equilibrium is exactly

$$x_v = \frac{1}{\deg v} \sum_{w \sim v} x_w,$$

for each free point $v$, in each coordinate. The springs’ total energy, the sum of the squared edge lengths, is a bowl-shaped function of the free positions, with one lowest point, and that lowest point is where every free vertex sits at the average of its neighbours.

In matrix language the equations are the graph’s Laplacian — the matrix a determinant that counts trees and the eigenvalue question both used — restricted to the free points and set equal to what the pinned points contribute. Restricted in that way it is invertible whenever the graph is connected and at least one point is pinned, because a vector the restricted Laplacian kills would be an equilibrium with every free point at the average of its neighbours and the boundary at nought, and such a vector must vanish. So there is always exactly one solution, whatever the graph. The theorem is about when that solution is a drawing.

Any start converges to it #

The single solution can be reached without solving anything, by doing what the springs would do.

Start the free points anywhere, and sweep through them repeatedly, moving each to the average of its current neighbours. Each sweep lowers the springs’ energy, the positions converge, and the limit is the unique solution — so the random start, with four crossings, is forgotten within a few sweeps. The method is Gauss–Seidel iteration, the oldest way to solve a system like this, and the figure runs it until successive sweeps move no point by more than a trillionth.

How fast it converges is a question about the graph, and it has an answer already met elsewhere. Moving each point to the average of its neighbours is one step of a random walk run backwards: the new position of $v$ is the expected position of a walker who starts at $v$ and takes one step. Repeating it is taking more steps, and the error decays at the rate the walk forgets where it started — the spectral gap of the walk with the pinned points made absorbing. A graph with a narrow bottleneck converges slowly; a well-connected one converges fast.

Where a random walk expects to leave #

The random-walk reading gives more than a rate. It says what the solution is.

Start a random walk at a free point $v$ and let it wander, each step to a neighbour chosen uniformly, until it first reaches a pinned point on the outer face. Where it arrives is random. Its expected position — the average of the outer points weighted by the chance of arriving at each — satisfies the averaging equation, because the walker’s first step goes to each neighbour with equal chance and the expected arrival point from there is that neighbour’s own. On the outer face the walker has already arrived. So the expected exit position obeys the same equations with the same boundary values as Tutte’s drawing, and by uniqueness it is Tutte’s drawing.

Each point of the drawing sits at the place a random walk from it expects to leave the graph. That is the discrete form of a classical fact about harmonic functions — a function that is the average of its values around every point is the expected value of its boundary values at a random walker’s exit — and two barriers and a fair game met its one-dimensional case, where the chance of reaching one barrier before the other is a straight line in the starting position. Tutte’s drawing is that straight line, run in two dimensions on a graph.

Why there are no crossings #

That the solution exists is easy. That it has no crossings is the theorem, and the key step is an old principle in a new setting.

No free point can be extreme. Take any direction in the plane and measure how far along it each point lies. A free point is the average of its neighbours, so unless all its neighbours are level with it, at least one is further along and at least one is less far. Following neighbours that are further along, a path can be walked from any free point that climbs strictly until it reaches the pinned outer face. This is the maximum principle for averages, and it has a geometric consequence: every free point lies inside the convex hull of its neighbours, and never at a corner of it.

From there, the argument that no two edges cross is a matter of counting angles. Around each free point, its neighbours are spread so that they do not all lie in any half-plane through it; around each face, the corners bend consistently the same way; and a sum over all the faces of the angles they turn through, compared with the total available, leaves no room for a face to fold over another. The details are delicate — Tutte’s proof is several pages, and a cleaner one using discrete analogues of differential forms was found by Steven Gortler, Craig Gotsman and Dylan Thurston in 2006 — but the engine is the maximum principle, and everything else is bookkeeping about how faces fit together.

Any face can be the outer one #

The theorem does not care which face is chosen to be outside, and different choices give genuinely different drawings. The prism with a triangle outside is a triangle inside a triangle, joined corner to corner. With a square outside it is a square with two points inside it, each joined to two corners of the square and to the other. Both are correct drawings of one graph, and both come from the same rule. The outer face is the only choice the method leaves, and for a graph whose faces are all alike, like the cube, there is nothing to choose at all.

For a graph with many faces the drawings the rule produces are recognisable: they are the pictures of polyhedra seen through one face.

The dodecahedron’s twenty points and thirty edges come out in three rings, every one of its eleven inner faces a convex pentagon. Nothing in the rule knows that the graph is the skeleton of a solid. It is the averaging that produces the picture everyone draws of the dodecahedron flattened, with the far face stretched round the outside — what geometers call a Schlegel diagram.

Unequal springs, and every drawing there is #

Nothing in the argument needed the springs to be equal. Give each edge its own positive stiffness and put each free point at the weighted average of its neighbours: the equations still have one solution, the maximum principle still holds — a weighted average with positive weights cannot be extreme either — and the drawing is still free of crossings with convex faces. In the random-walk reading, the weights are the walker’s preferences, and a walk that favours some edges is still a walk, as a chain that runs the same backwards showed for walks on weighted graphs in general.

The weights buy something the equal version cannot give. Michael Floater proved in 1997 that the theorem survives even when each point uses its own positive weights for its neighbours, with no requirement that the weights be symmetric like springs. And the converse is immediate: in every drawing of a three-connected planar graph with straight edges, convex faces and a given convex outer face, each inner point lies strictly inside the polygon of its neighbours, so it is a positive weighted average of them — and that drawing is the averaging drawing for those weights. So the averaging rule is not one drawing among many: with the weights free it is all of them, and choosing weights is choosing a drawing. That is how the method is used in computer graphics, where a triangulated surface — a face, a statue, a map of a planet — has to be flattened onto a picture without folds so that an image can be painted onto it. The weights are chosen to keep angles or areas as close to the surface’s as possible, and the theorem guarantees that whatever weights are chosen, the flattening never folds over itself.

A second canonical drawing #

The averaging drawing is not the only canonical picture of a planar graph, and its rival is instructive precisely because it is so different.

Every flat graph is a pile of circles — Koebe’s theorem — draws each point as a circle, with two circles touching exactly when their points are joined, and the picture is unique up to the maps that carry circles to circles. It too is determined by the graph alone, and for a triangulation it too is the shadow of a convex solid, this time one whose edges all touch a sphere. But it is found by solving non-linear equations in the circles’ radii, iteratively and approximately, where the averaging drawing is a single linear system. The circle packing is geometrically beautiful and computationally hard; the averaging is plain and exactly solvable, and which one a problem wants depends on whether it needs the circles or only the flatness.

The condition: no two points cut it apart #

Tutte’s theorem needs one hypothesis beyond planarity, and the averaging shows exactly why.

A graph is three-connected if removing any two points leaves it connected. The cube, the prism and the dodecahedron are three-connected. The next graph is not.

Two extra points hang between opposite corners of a square and are joined to each other. Each is the average of the two corners and the other extra point; solving, both are the midpoint of the diagonal, on top of each other, and their edges lie along one line. The equations have their unique solution and the solution is not a drawing. The pair of corners that separates the graph is where it collapses: the part hanging between them has nothing pulling it sideways, because everything it is attached to lies on one line.

That is the general mechanism. If two points separate the graph, the piece they cut off is attached to the rest only through them, the maximum principle confines it to their segment, and it lands flat on the line between them. Three-connectedness is exactly the condition that every piece is pulled from at least three directions. And it costs nothing in generality: every planar graph can be made three-connected by adding edges inside its faces, drawn by averaging, and the added edges deleted — which is one way to prove Fáry’s theorem.

Correct, and shrinking #

The drawings are correct and they can be terrible to look at, for a reason the next graph makes plain.

Nest four triangles and join each to the next by six edges. Every drawing of this graph without crossings has to nest the triangles, and averaging nests them evenly: each triangle comes out about $0.15$ of the size of the one outside it, and the innermost is a few thousandths of the outermost. With twenty nested triangles the innermost would be smaller than an atom on a page a metre wide. The drawing is exact and useless, and not because of rounding: the positions are what the equations say.

That is a genuine limitation of averaging and not of straight-line drawing. Hubert de Fraysseix, János Pach and Richard Pollack showed in 1990, and Walter Schnyder by a different route the same year, that every planar graph on $n$ points has a straight-line drawing with all its points on a grid of about $n$ by $n$ — so the ratio of the longest to the shortest distance never needs to be worse than about $n$. The nested triangles need a grid of about $2n/3$ in each direction, whatever method is used. Averaging gives up that economy for a different virtue: its drawing is canonical, determined by the graph and one face, and it comes with a proof.

A drawing that is the shadow of a solid #

The dodecahedron’s picture points at the deepest consequence of the method.

Ernst Steinitz proved in 1922 that the graphs of convex polyhedra — the networks of corners and edges of solids like the five regular ones — are exactly the three-connected planar graphs. One direction is an observation; the other, that every such graph is the skeleton of some convex solid, is a construction, and Tutte’s drawing supplies the first half of a modern one. An equilibrium of springs is a set of forces balanced at every free point, and James Clerk Maxwell observed in 1864 that a balanced system of forces on a planar drawing can be lifted: each face raised to a plane in three dimensions so that the whole becomes a polyhedral surface whose creases carry the forces. With the springs’ tensions as the forces and the outer face treated suitably, the lifted surface is convex, and the drawing is its shadow.

So the averaging, read as physics, produces not only a flat drawing but a solid whose shadow it is. A three-connected planar graph is drawn flat by springs and stood up by the same springs’ tensions, and that is one of the shortest roads to Steinitz’s theorem.

The drawings and what they leave out #

Every graph drawn here is small and hand-built. The cube, prism, dodecahedron, nested triangles and the collapsing square are chosen to show one feature each; the theorem is about every three-connected planar graph, and nothing larger is drawn.

The absence of crossings is checked, not seen. For each drawing the figure tests every pair of edges and refuses to draw if two cross, and that is a statement about these drawings. The proof that averaging never produces a crossing in a three-connected planar graph is described above, not performed.

The random-walk reading is described and not simulated. No walker is released in any figure; the identification of the drawing with expected exit positions follows from uniqueness of the solution, and a figure that averaged thousands of simulated walks would converge to the same picture slowly and prove nothing more.

Still open: straight edges of whole-number length #

Straight edges without crossings are always possible, on a grid of size about $n$, and the grid question itself has a gap that is not closed: the smallest grid that suffices for every planar graph lies between about $2n/3$ and about $n$ in each direction, and where exactly is not known.

A stranger question is about lengths. Can every planar graph be drawn with straight edges, no crossings, and every edge a whole number long? Heiko Harborth conjectured in the 1980s that it can. It is known for some families — the planar graphs in which every point has three neighbours, by a theorem of Jim Geelen, Anjie Guo and David McKinnon in 2008 — and open in general, even though the rational points on circles are dense enough that most individual constraints can be met, and the difficulty is meeting all of them at once.

Drawing by solving #

The habit worth keeping is the replacement of a search by an equation.

A drawing without crossings is a global object — every pair of edges has to avoid every other — and the instinct is to build it by trial and repair. Tutte’s rule is local: each point looks only at its neighbours and sits at their average. The global property comes out of the local rule because averages cannot be extreme, and because a three-connected graph pulls every piece from enough directions that nothing can fold. A condition that must hold everywhere is produced by a condition that holds at every point, and the linear algebra guarantees there is exactly one way to satisfy it.

The same local rule turned out to be a spring network in equilibrium, the expected exit of a random walk, and the shadow of a convex solid. Those are four descriptions of one set of positions, and each of them explains a different property of the drawing: its uniqueness, its convergence, its convexity, and its connection to the solids whose skeletons these graphs are.