One-forms and Tutte-like Embeddings


February 14, 2005


Steven J. Gortler


Harvard University


In 1962, Tutte presented a simple algorithm to draw a planar graph using straight lines. This algorithm has become the primary method that is used in computer graphics for flattening meshes. Mesh flattening is the first step in many geometric processing algorithms, such as texture mapping. Though Tutte’s algorithm is simple, his proof of correctness was anything but.

In this talk, I will describe some properties of one-forms on meshes, and show how this can be used to provide an elementary proof of the correctness of Tutte’s algorithm. These properties will also allow us to analyze some natural generalizations of Tutte’s algorithm such as flattening closed meshes of arbitrary genus.


Steven J. Gortler

Steven (aka Shlomo) Gortler, a native of Seattle, is the Robert I. Goldman Professor of Computer Science at Harvard University. He is currently on sabbatical as a visitor to the University of Washington. Shlomo’s main area of research is computer graphics, specializing in rendering and geometry, but is often convinced to work on other things as well.