graph

Circle packing theorem

Recently I heard about this surprising theorem. I already knew about Fáry’s theorem: if a simple graph can be drawn on the plane without crossing edges (i.e. if the graph is planar), then it can always be drawn in such a way that all edges are non-crossing straight lines. Hence, restricting to straight-line edges doesn’t give a strictly smaller class of planar graphs. I found this to be quite surprising already.

However, much more is true: you can always draw a simple planar graph in the plane in such a way that you can place non-overlapping circles on the vertices, such that two circles touch if and only if the corresponding vertices are joined by an edge. In particular, the drawing clearly satisfies the result of Fáry’s theorem. This result is called the circle packing theorem.