Tutte embedding and how to draw a graph
Definitions
Tutte embedding is method to generate drawing of 3-(vertex)-connected graphs. With the following definitions.
Definition A graph $G$ is called $k$-vertex-connected if removing any $k$ vertices from $G$ would let $G$ remain connected.
Definition A drawing $z$ of graph $G$ is a embedding of $G\rightarrow \mathbb{R}^2$. $G$ is called planar if such a drawing exists.
Definition A Tutte embedding of planar graph $G$ is a drawing $z$ of $G$ such that
- There is a face $F$ of $G$ such that $z$ maps the vertices of $F$ to the corners of a strictly convex polygon so that every edge of the face joins consecutive corners of the polygon
- Every vertex not in $F$ lies at the barycenter of its neighbors.
- Each edge is represented as a straight line.
By definition Tutte embedding is free from self-intersections because it is a drawing.Theorem
This is not the initial statement of theorem, but I have tailored it a bit to make it rigorous (in my taste)
Theorem (Tutte 1963) Given 3-connected planar graph $G$ with a planar drawing $z$ (edges are possibly curves), there is a external loop $\partial f_e$ (proof by induction, add vertices and edges that are not in interior). Place $\partial f_e$ on the boundary of a planar strictly convex polygon $P$ and place the vertices on external loop onto the conners of $P$. Place each internal vertex at the barycenter of its neighbors, connect edges by straight lines. We get a Tutte embedding.
Proof It amounts to prove that the edges will not intersect each other. In fact, a stronger statement is “the internal faces are strictly convex themsel”
Application and extension
In computer graphics, a general (good enough) mesh is 3-vertex-connected, which enables a fast algorithm for parametrization.