Tutte seminar - Jim Geelen

How to draw a graph

Abstract:

Tutte proved that every 3-connected planar graph admits a convex embedding; that is, an embedding in which each face is bounded by a convex polygon. The result itself is attractive, but the method used is truly stunning. Embed the outer face as a convex polygon, now imagine the edges as springs and take a stable-state embedding. It's planar and convex! We will see why.

This talk is presented in honour of William T. Tutte on the tenth anniversary of his death.