|
Friday, June 1, 2012 |
|
|
|
|
How to draw a graph |
|
|
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.
|