How to draw a graph
|Affiliation:||University of Waterloo|
|Room:||Mathematics & Computer Building (MC) 5158|
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.
200 University Avenue West
Waterloo, ON N2L 3G1