One-forms and Tutte-like Embeddings

Опубликовано 6 сентября 2016, 5:21

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.