Tutte Embedding Animator

When I was in my third year of university I took the class CO 342: Introduction to Graph Theory as an elective. Despite the naming of the course, students are already expected to have some graph theory knowledge introduced in MATH 239: Introduction to Combinatorics. In this course, Dr. Peter Nelson exposed me to the idea of a Tutte Embedding.

A Tutte Embedding is a special kind of drawing for simple 3-vertex-connected planar graphs. Essentially, after fixing an outer polygon - one can simply solve a system of linear equations such that each vertex is the average position of all its neighbours. Given these constraints, Tutte proved the remarkable result that this drawing is always crossing-free, and each face in the embedding is convex.

I found this astonishing. I distinctly remember the class finishing on a Friday and staying up until 2am the next Saturday morning programming a website to animate the result. Upon seeing it Dr. Nelson graciously gave me some extra credit and has since used it to demonstrate the concept to other offerings of the course.

Here is a GIF of me using the website:

The website can be found here and the source code is on GitHub. I’ll warn that both the design of the website and the source code are a little ugly - the project was made in haste since we were only a few weeks away from exams. Nevertheless, I think it’s a great demonstration of the power of animation and visuals to excite people about mathematics as well as display its beauty.