Category: graph theory

Photo

Photo

We’ll pick this up next time, and I’ll explain…

We’ll pick this up next time, and I’ll explain it again for people who didn’t understand it. For example, me.

Photo

Circle packing theorem

:

Recently I heard about this surprising theorem. I already knew about : 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 .

A complete graph on 40 equally spaced vertices, with close ups…

A complete graph on 40 equally spaced vertices, with close ups of regions.