Tutte Colloquium - Jim Geelen

Title: How Tutte drew a graph

Abstract:

In his 1963 paper on "How to draw a graph", Tutte described a surprisingly simple and beautiful algorithm for drawing a planar graph. The idea is to fix an embedding of one face as a convex polygon and to consider the edges as springs in order to determine the locations of the other vertices. For three-connected planar graphs this always results in a planar straight-line embedding. I will describe a new proof of this theorem that I found with Bert Gerards. In many respects Tutte’s proof is more illuminating, but it is a good excuse to talk about this gem of graph theory.