Tutte embedding

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Tutte embedding is a simple, reliable way to draw certain graphs without crossings. It applies to simple planar graphs that are 3-vertex-connected. The key idea is to fix the outer boundary as a convex polygon and place every interior vertex so that it sits at the average position of its neighbors. This makes the interior coordinates satisfy a pair of linear equations, one for x and one for y, which together determine a unique placement when the outer face is fixed.

Why this works and what you get
- The outer face is a convex polygon, and each interior vertex is the average (the barycenter) of its neighbors’ positions.
- Solving the linear system for the interior vertices yields a planar drawing with straight edges.
- Tutte’s spring theorem guarantees this solution is crossing-free and all faces in the drawing are convex. The idea is to think of the graph as a network of springs: the unique equilibrium places interior vertices at the average of their neighbors.

A concrete example
- Consider the graph of a cube. Fix one square face as the outer boundary with its four corners at the corners of a unit square.
- Place the other four vertices at the points whose coordinates are the fractions 1/3 and 2/3. In this arrangement, each interior vertex is the average of its neighbors, so you obtain a Tutte embedding.

How it’s found and what it means
- The placement of the interior vertices is obtained by solving 2(n − h) linear equations in 2(n − h) unknowns, where n is the number of vertices and h is the number on the outer face. For 3-connected planar graphs, this system is well-behaved and has a unique solution.
- Practically, you can compute the embedding in polynomial time (for example, with Gaussian elimination).

Connections to geometry and polyhedra
- Steinitz’s theorem tells us that every 3-connected planar graph is the graph of a convex polyhedron, so Tutte embeddings provide a way to realize these graphs as convex polyhedra (Schlegel diagrams).
- There’s a related interpretation via the Maxwell–Cremona correspondence: a planar embedding can be viewed as a 3D convex polyhedron projection if the edges carry balanced forces. For Tutte embeddings with a triangular outer face, you can arrange forces so the balance also holds on the outer boundary.

Applications and extensions
- In geometry processing, Tutte embeddings are used for 2D parameterizations of 3D surfaces (disk topology). The goal is to map a surface to a 2D disk while preserving shape as much as possible by treating vertices as masses connected by springs. Edges’ stiffness is often set based on original edge lengths to reflect the surface’s geometry; boundary vertices are fixed to close the disk.
- Variants include using weighted averages (instead of a straight average) and choosing boundary conditions to suit the application.
- If a graph isn’t 3-connected, you can add extra edges to make it 3-connected, compute the embedding, and then remove the added edges.
- Beyond the plane, researchers have extended ideas like Tutte’s to higher-genus surfaces and other related representations, and there are related methods for circle packings and higher-dimensional generalizations.

In short, a Tutte embedding gives a clean, guaranteed-to-be-crossing-free straight-line drawing of a 3-connected planar graph by fixing the outer boundary and placing every interior vertex at the average of its neighbors. It connects graph drawing, polyhedra, and practical surface parameterization in a single, powerful idea.