One of Oded Schramm's less-well-known but better-named results is his "monster packing theorem", a far-reaching generalization of the famous circle packing theorem of Koebe, Andreev, and Thurston.

The graph of the icosohedron as a contact graph of circles

Here, a packing is a set of geometric shapes with disjoint interiors, whose intersection graph represents a given planar graph. For instance, the circle packing theorem states that every planar graph can be represented as the intersection graph of interior-disjoint circles. But what if we want to pack shapes other than circles? What if we don't even want all the vertices to be represented by the same shape as each other? That's where the monster packing theorem comes in.

The theorem itself is a little difficult to explain. It involves monsters. A monster has a body formed by a collection of shapes, connected into a tree (much like the fingers, hands, arms, ears, nose, head, neck, and other appendages of a human body can be connected into a tree). It can be described by a continuous function whose input is a list of numerical parameters specifying how far each of its appendages should be twisted around its neighboring appendage towards the root of the tree. The output of the function says what shape each appendage takes. Subject to some technical conditions on how this function behaves, the theorem guarantees that the monster can always fold itself up into a nice packing, with no self-overlaps or missing adjacencies, by choosing the right input parameters.

The graph of the icosohedron as a contact graph of equilateral triangles

What is easier to explain are the consequences of this for representing graphs by packings. We suppose that each vertex of a given graph has a prototype shape (a circle, pentagon, etc) and that it should be represented by a copy of that shape that has been scaled and shifted but not rotated (the technical word for this kind of transformation is a "homothety"). Then

  • If one vertex of a maximal planar graph is chosen to be the outside one, and has a smooth simply-connected prototype, and every other vertex has a smooth strictly-convex prototype, then there always exists a packing whose intersection graph is the given graph, in which every vertex is represented by a homothetic copy of its prototype. (I think this can also be generalized to polygons in which all angles are greater than 120 degrees; for instance, regular octagons).

  • Suppose that a triangle of three vertices in a maximal planar graph are chosen to be the outside ones, each is associated with a non-empty contiguous curve, and these three curves together form a simple closed curve. Suppose also that each other vertex has a convex prototype with nonempty interior. Then there always exists a packing whose intersection graph is a supergraph of the given graph, in which every vertex is represented either by a homothetic copy of its prototype or by a point.

The second version can handle a wider choice of prototype shapes, but the possibility of degenerate packings (with extra adjacencies and/or shapes that shrink down to points) makes it a little harder to use. For instance, it is not true that every maximal planar graph can be represented by an intersection graph of interior-disjoint homothetic equilateral triangles (what you would like the theorem to state) but it is true for every 4-vertex-connected planar graph, because the lack of separating triangles makes it impossible for their packings to degenerate (see Felsner and Francis for a more constructive but unproven method of generating these representations). Similarly, every maximal planar graph without separating four-cycles can be represented by a partition of a rectangle (representing one outer vertex) into touching squares; however, there is no way to avoid the four-cycles (pairs of triangles) that surround individual edges of the input graph. This may cause quadruples of squares to meet at a single point; two diagonally opposite squares are adjacent in the graph, and the other two are not, but there is no way to tell visually which is which.

The graph of the icosohedron as a contact graph of squares

The icosahedron gives a nice example of a maximal planar graph without separating triangles or quadrilaterals. The images above show three of its representations: as a circle contact graph, as a triangle contact graph (redrawn from Felsner and Francis), and as a set of touching squares. The circle and square representations have a single outside vertex, but the triangle representation has three. The circle and triangle representations have the same outside shape, but the square representation has a rectangle outside. In the triangle representation, the nine white triangles and three outer edges represent the 12 vertices. The blue triangles in the backgraph can be thought of as as a representation of the dual dodecahedron, but a degenerate one; there should be another blue triangle at the point where the six triangles meet in the center, but it has degenerated to a point.