The Koebe embedding theorem states that any planar graph can be realized by a collection of disjoint circles, meaning that each circle corresponds to a vertex of the graph and two circles are tangent if and only if they are connected by an edge. If all faces of the graph are triangles, the realizations are unique up to inversion: one can get from any realization to any other by a sequence of inversions. This uniqueness property is closely related to Mostov rigidity of hyperbolic manifolds.

The circles below represent the skeleton of an octahedron, a planar graph with six vertices and twelve edges. Therefore there are six (blue) circles, each tangent to four others. The red arcs form a drawing of the graph itself. The red circles are also the bisectors for the three pairs of nontangent circles, and also pass through the tangencies of three rings of four tangent circles, each of which forms an instance of Steiner's porism. The orthogonal circles through each triple of three mutually tangent circles (not shown) are the eight Apollonian circles of the three red circles and form a realization of the planar dual graph, a cube.

If you were running Java, you'd see a nice animation instead of this gif.

Warren Smith has found fast algorithms for approximating the locations of a circle realization of a graph, but finding exact locations seems to be computationally difficult (in that it involves finding the roots of high-degree polynomials, while standard models of exact computation assume only the ability to handle bounded degree). The examples on these pages were all compass-and-straightedge constructible, but some Koebe embeddings are not. For instance, any realization of the heptagonal bipyramid (i.e., a seven-circle Steiner porism) could be used to construct a regular heptagon (known to be impossible) since seven circles through triples of its tangencies meet at a common point and form angles of pi/7 there.

Finally, it seems to be unknown which nonplanar graphs can be realized as tangencies of (non-disjoint) circles. Any set of disjoint circles has a circle with degree at most five, but nondisjoint circles can have arbitrary degree (for instance, any hypercube skeleton can be realized). A better characterization of these graphs might shed some light on the question we started with, Ringel's problem of bounding their chromatic number.

Animation created by Cinderella.
From the Geometry Junkyard, computational and recreational geometry.
David Eppstein, Theory Group, ICS, UC Irvine.

Last update: .