Every flat graph is a pile of circles

A graph is planar when it can be drawn in the plane with no edges crossing. That is a statement about the existence of a drawing, and the usual drawings look arbitrary: vertices anywhere, edges any shape, and a thousand pictures of the same graph with nothing to choose between them.

Koebe’s theorem says the arbitrariness is an illusion. Every planar triangulation is the tangency pattern of a packing of circles — one circle per vertex, two touching exactly when their vertices are joined — and for a triangulation of the sphere that packing is unique up to Möbius transformations.

What the packing has to satisfy #

The statement needs one restriction and it is worth getting out of the way. The theorem is about triangulations — planar graphs every one of whose faces is a triangle. A planar graph that is not a triangulation can always be made into one by adding edges, and the packing of the enlarged graph is a packing whose tangencies include the original’s; so the restriction costs nothing except that a general planar graph’s packing is not unique. Whether a graph is planar at all is a separate question with a separate answer, and this theorem assumes it settled.

Assign a radius to every vertex. Three circles that pairwise touch determine a triangle, and the triangle’s angle at each circle is fixed by the three radii: the sides are $r_i + r_j$, $r_j + r_k$, $r_k + r_i$, and the angle follows from the cosine rule.

Now the condition. Go round an interior vertex, taking its neighbours in cyclic order. The triangles at that vertex must fit together without gap or overlap, so their angles must add to exactly a full turn.

That is one equation per interior vertex, in the radii of that vertex and its neighbours. Boundary vertices have no such condition, so their radii can be chosen; the theorem is that once they are, the interior radii are determined and positive.

The whole of the geometry is a single condition repeated at every interior vertex: the angles add to a full turn. Everything else — where the circles sit, how large the picture is — follows.

Solving it, and why the solution is unique #

The equations are not linear and there is no formula. What there is, is a monotonicity that makes them easy.

Fix every radius but one and consider the angle sum at that vertex as its own radius varies. Shrinking a circle makes its neighbours subtend larger angles at it, so the sum increases; growing it makes the sum decrease. The angle sum is therefore a strictly decreasing function of the vertex’s own radius, running from more than a full turn to less, so there is exactly one radius making it a full turn and it can be found by bisection.

There is a second way to see the same thing, and it explains why the iteration is so well behaved. The angle sum at a vertex depends only on the ratios of the radii around it, so scaling everything changes nothing; and increasing any neighbour’s radius decreases the angle it subtends. The system is therefore monotone in a way that makes each sweep a contraction on the logarithms of the radii, which is the standard reason an iteration of this shape converges — the same reason a map that shrinks every distance has exactly one fixed point.

Thurston’s algorithm is that observation applied repeatedly: sweep through the interior vertices, set each one’s radius to the value making its own angle sum correct, and repeat. The sweeps converge, and the figure reports how many it took — twenty-nine, to twelve decimal places.

The monotonicity is doing two jobs. It makes the iteration converge, and it makes the answer unique — two different solutions would have to differ at some vertex, and the vertex where the ratio between the two solutions’ radii is largest cannot have its angle sum right in both. That is the standard uniqueness argument for this kind of system and it needs no analysis beyond the monotonicity.

Laying it out, and what the layout proves #

Radii are not a picture. Turning them into one is a walk, and the walk is where the angle condition earns its keep.

Place any circle, then place one of its neighbours beside it. Every subsequent circle is placed by the angle at a vertex whose position is already known: go round that vertex, placing each neighbour at the angle the radii dictate. Since the angles at an interior vertex add to a full turn, the walk round it closes — the last circle placed lands on the first, which was placed earlier by a different route.

That closing is the only check the layout needs, and it is not automatic. If the radii were slightly wrong, the walk round each vertex would fail to close by a small amount, and the failures would accumulate into a visibly broken picture. The figure reports the worst closure error over all seven interior vertices: about $10^{-12}$, which is the arithmetic’s own noise.

Two further properties are then measured rather than assumed. Every edge of the triangulation is a tangency of the two circles it joins, to the same precision. And no two circles whose vertices are not joined overlap — which is the half of the theorem that makes the packing a picture of the graph rather than merely a collection of circles satisfying some equations.

Where the construction stops being safe #

The generator refuses some boundary radii, and the refusal is worth explaining because it is a real limitation rather than a defensive check.

Solving the angle conditions and walking the layout gives a packing that is locally correct everywhere: every vertex’s flower closes, and every edge is a tangency. It does not guarantee that the whole picture is embedded. Push the boundary radii far enough apart — one boundary circle three or four times another — and the layout wraps around on itself, so two circles whose vertices are not joined overlap.

That is not a failure of the algorithm. It is the difference between a locally univalent packing and an embedded one, and pinning the second down needs a stronger normalisation than choose the boundary radii: the clean statement fixes the boundary circles to be tangent to a common circle instead, and then embeddedness comes free.

So the figures here check embeddedness rather than assuming it, and refuse the inputs where it fails. A picture of a packing that overlaps itself, captioned as a packing, would be exactly the kind of claim this collection exists not to make.

Why “up to Möbius” is the right qualification #

The uniqueness statement has a qualifier, and it is the reason this rung sits at the top of a ladder about inversion.

For a triangulation of the sphere — no boundary at all — there are no free boundary radii, and the packing is unique up to Möbius transformations and reflections. That is exactly the group two inversions generate, and it is the largest group that could possibly be there: a Möbius map carries circles to circles and tangencies to tangencies, so it carries a packing to a packing of the same graph, and no theorem can distinguish the two.

So the theorem is as sharp as a theorem can be. It says the packing is determined by the combinatorics, and the freedom left over is precisely the freedom that no statement about circles and tangencies could ever remove. That is a much stronger statement than a drawing exists, and it converts a planar graph from a thing with many pictures into a thing with one picture and a six-parameter family of viewpoints on it.

What the theorem is good for #

Three uses, and they are not the ones a reader would guess from the statement. None of them is drawing a graph, which is what the theorem appears to be about.

A canonical drawing. Two graphs that will not lie flat is a statement about which graphs are planar; this is a statement about how to draw the ones that are. A circle packing gives a drawing with no arbitrary choices, which is what an algorithm wants when it has to compare two drawings or decide whether two graphs are the same. Colouring a planar map is a question about the graph and not the drawing, and so is nearly everything else worth asking — but an algorithm still has to hold a drawing, and holding a canonical one is worth a great deal.

A discrete conformal map. The packing of a triangulated region is a discrete analogue of the conformal map from a disc onto that region, and refining the triangulation makes the analogy exact — Rodin and Sullivan proved in 1987 that packings of finer and finer hexagonal triangulations converge to the Riemann map. That gives a way of computing conformal maps by solving angle conditions, with no analysis in the algorithm at all.

A proof of rigidity. Andreev’s version characterises which patterns of circles with prescribed intersection angles exist and shows they are rigid, and Thurston used it in the study of three-dimensional geometry. The theorem is doing structural work there rather than producing pictures.

What the theorem replaced #

It is worth knowing what drawing a planar graph looked like before, because the contrast is the argument for having a canonical picture at all.

The standard existence result is Fáry’s: every planar graph can be drawn with straight edges. That is a fine theorem and it determines nothing — the vertices may go almost anywhere, and two people applying it to the same graph produce two unrelated pictures. Every subsequent result in graph drawing has been about choosing: draw it on a small grid, draw it with few bends, draw it so that the areas of the faces are prescribed. Each is a different criterion and each produces a different drawing.

The circle packing is not another criterion. It is the drawing the graph’s own combinatorics forces, and the only choice left in it is a change of viewpoint. That is a different kind of result: not here is a good drawing by some standard, but here is the drawing, and here is exactly how much of it was arbitrary.

The same distinction separates a normal form from a heuristic anywhere in mathematics. Reducing a matrix to a canonical shape is worth more than reducing it to a convenient one, because two objects have the same canonical form exactly when they are the same object — and a heuristic answers no question at all about equality.

What the pictures cannot show #

The refused inputs are not shown either. A packing that overlaps itself would be the illustration the section above wants, and the generator produces none, because it refuses to draw one.

One triangulation is one triangulation. Nineteen circles with seven interior vertices is the smallest instance in which the angle condition has anything to do, and the theorem is about every planar triangulation.

The boundary case is drawn and the sphere case is described. With boundary radii free, the packing is unique once they are chosen; the clean statement — unique up to Möbius — is about triangulations of the sphere, which have no boundary and cannot be drawn in a plane without choosing a face to be the outside.

The convergence is reported and not shown. Twenty-nine sweeps of an iteration is a number; a figure of it would be a picture of radii moving, which is a picture of an algorithm.

The uniqueness is argued and not tested. Nothing here starts the iteration from a different initial guess and checks that it arrives at the same radii, which would be the honest experimental version of the uniqueness claim.

And the tangency graph is drawn over the circles. The lines between centres are there to make the correspondence readable, and they are not part of the packing — the packing is the circles, and the graph is what the tangencies happen to be.

Where the ladder goes next #

This closes the ladder. It began with a map that trades circles for lines, and each rung asked the same question of it: what can this map do to a problem? It could solve a tangency problem by moving one circle to a point; it could generate an infinite packing by turning a quadratic’s second root into a subtraction; composed with itself it became a group with an invariant.

And it ends at a theorem where the map is not a technique but the answer’s own margin of error. The packing exists, it is determined, and what it is determined up to is the group the first rung’s map generates.

Sideways: the conformal maps this makes computable are the same ones that carry the inside of any simple closed curve to a disc, which is the analytic route to Schoenflies’s theorem; and the rigidity here is the same phenomenon as a triangulated framework having no motions, counted rather than proved.

What is worth carrying away #

A theorem that determines an object up to a group is stronger than one that merely produces the object, and reading it means reading the group.

Koebe’s theorem does not say a planar graph can be drawn as touching circles; that would be an existence statement of the ordinary kind. It says the drawing is unique up to Möbius transformations — and since a Möbius map is precisely a map preserving circles and tangencies, the freedom it leaves is the freedom nothing in the statement could remove. The qualification is not a weakness of the theorem; it is the theorem’s claim to be complete, and a reader who skips over up to has missed the part that makes it worth having.