Penny graphs

A penny graph can be created from a non-overlapping arrangement of unit circles on a flat surface. Each vertex of the graph corresponds to one of the unit circles, and two vertices are connected by an edge if and only if the corresponding unit circles touch. The graph below is the penny graph arising from the arrangement of coins in the photograph. The graph has 11 vertices and 19 edges, because it is constructed from an arrangement of 11 pennies with 19 points of contact.

A penny graph can always be drawn in the plane in such a way that none of its edges cross, which means that penny graphs are examples of planar graphs. An example of a non-planar graph arises from the three utilities problem, which asks whether it is possible to connect each of three houses to three different utilities (water, gas, electricity) without any of the nine supply lines crossing directly above or below each other. The answer, as illustrated below, turns out to be “no”.

The graph that models the three utilities problem is known as K_3,3. The three yellow vertices below can be identified with the three houses, and the three purple vertices with the three utilities. The graph K_3,3 is not planar, which means that it is impossible to draw it on a piece of paper without any of the lines crossing. 

Another graph that cannot be drawn in the plane without crossings is the complete graph K₅, shown below. This consists of 5 vertices, numbered 1 up to 5, each of which is connected to each of the others by an edge. Notice that K₅ has 10 edges, which explains why a total of 10 handshakes occur when 5 people all shake hands with each other. Kuratowski’s Theorem proves that any graph that is not planar must contain a copy of either K₅ or K_3,3, in a sense that can be made precise. It follows that the graphs K₅ and K_3,3 exemplify the two fundamental ways in which a graph can fail to be planar. 

If we try to draw graphs on the surface of a torus, things are very different. The recent paper K5 and K3,3 are Toroidal Penny Graphs by Cédric Lorand uses explicit coordinates to prove that, on the flat square torus, K₅ and K_3,3 can both be constructed as penny graphs. The flat square torus can be thought of as a square in which the left and right edges have been identified with each other, and the top and bottom edges have also been identified with each other.

Another way to think of the flat square torus is as an infinite wallpaper-like tessellation of copies of the same square. From this point of view, all the yellow circles labelled “3” in the picture above are the same circle. Notice that each yellow circle touches three purple circles labelled 4, 5, and 6, and that each purple circle touches three yellow circles labelled 1, 2, and 3. It follows that the contact graph of this arrangement of circles is K_3,3.

Something similar can be done with the complete graph K₅, as shown above. In this case, each circle touches all four of the others. Incidentally, this arrangement turns out to be the densest way to pack five circles in a flat square torus.

Lorand also proves that it is possible to draw the complete graphs K₆ and K₇ on the flat square torus without intersections, although not as penny graphs. The paper also discusses some historical and computational aspects of the problem. For example, in 1974, John Hopcroft and Robert Tarjan found an efficient (linear time) algorithm to test whether or not a graph is planar. In contrast, Peter Eades and Nicholas C. Wormald proved in 1990 that the problem of deciding whether an arbitrary graph can be embedded in the plane as a penny graph is NP-hard.

---

Picture credits and relevant links

The diagram of the penny graph is by Syp and appears on Wikipedia.

The diagram of the three utilities problem is by Cmglee and appears on Wikipedia.

The photograph of the pennies is my own, and the other graphics are based on the diagrams in the paper by Cédric Lorand.

Kuratowski’s Theorem is named after Kazimierz Kuratowski (1896–1980).

Substack management by Buzz & Hum.