Tutte’s Spring Embedding Theorem

Our first C&O Prof Talk of the term is right around the corner! Title: Tutte’s spring embedding theorem Speaker: Jim Geelen, Department of Combinatorics and Optimization Abstract: In 1963, Tutte proved that any 3-connected planar graph admits an embedding such that each face is bounded by a convex polygon. He proved the result by pre-embedding the outer face as a polygon and then considering the edges of the graph as springs. As a consequence to the proof one gets a very novel algorithm for planarity testing. Oct. 29, 4 - 5 pm at MC 5501 Pizza and refreshment available for members.