Tutte embedding

If the outer polygon is fixed, this condition on the interior vertices determines their position uniquely as the solution to a system of linear equations.

Then, if the remaining four vertices are placed at the four points whose x and y coordinates are combinations of 1/3 and 2/3, as in the figure, the result will be a Tutte embedding.

This embedding can be found in polynomial time by solving the system of equations, for instance by using Gaussian elimination.

According to the Maxwell–Cremona correspondence, a two-dimensional embedding of a planar graph forms the vertical projection of a three-dimensional convex polyhedron if and only if the embedding has an equilibrium stress, an assignment of forces to each edge (affecting both endpoints in equal and opposite directions parallel to the edge) such that the forces cancel at every vertex.

For a Tutte embedding, assigning to each edge an attractive force proportional to its length (like a spring) makes the forces cancel at all interior vertices, but this is not necessarily an equilibrium stress at the vertices of the outer polygon.

In this way, Tutte embeddings can be used to find Schlegel diagrams of every convex polyhedron.

Tutte's method minimizes the total distortion energy of the parametrized space by considering each transformed vertex as a point mass, and edges across the corresponding vertices as springs.

The tightness of each spring is determined by the length of the edges in the original 3D surface to preserve the shape.

But when no further constraints are applied, the solution that minimizes the distortion energy trivially collapses to a single point in the parametrized space.

Therefore, one must provide boundary conditions where a set of known vertices of the 3D surface are mapped to known points in the 2D parametrized space.

One common way of choosing such boundary conditions is to consider the vertices on the largest boundary loop of the original 3D surface which can be then constrained to be mapped to the outer ring of a unit disk in the 2D parametrized space.

Note that if the 3D surface is a manifold, the boundary edges can be detected by verifying that they belong to only one face of the mesh.

Applications of parametrization in graphics and animation include texture mapping, among many others.

Colin de Verdière (1991) generalized Tutte's spring theorem to graphs on higher-genus surfaces with non-positive curvature, where edges are represented by geodesics;[3] this result was later independently rediscovered by Hass & Scott (2015).

[4] Analogous results for graphs embedded on a torus were independently proved by Delgado-Friedrichs (2005),[5] by Gortler, Gotsman & Thurston (2006),[6] and by Lovász (2019).

[7] Chilakamarri, Dean & Littman (1995) investigate three-dimensional graph embeddings of the graphs of four-dimensional polytopes, formed by the same method as Tutte's embedding: choose one facet of the polytope as being the outer face of a three-dimensional embedding, and fix its vertices into place as the vertices of a three-dimensional polyhedron in space.

As they show, the system of equations obtained in this way is again non-degenerate, but it is unclear under what conditions this method will find an embedding that realizes all facets of the polytope as convex polyhedra.

[8] The result that every simple planar graph can be drawn with straight line edges is called Fáry's theorem.

A graph is k-vertex-connected, but not necessarily planar, if and only if it has a convex embedding into (k −1)-dimensional space in which an arbitrary k-tuple of vertices are placed at the vertices of a simplex and, for each remaining vertex v, the convex hull of the neighbors of v is full-dimensional with v in its interior.

If such an embedding exists, one can be found by fixing the locations of the chosen k vertices and solving a system of equations that places each vertex at the average of its neighbors, just as in Tutte's planar embedding.

In this method, each vertex is moved to or towards the average of its neighbors' positions, but this motion is only performed for a small number of iterations, to avoid large distortions of element sizes or (in the case of non-convex mesh domains) tangled non-planar meshes.

Force-directed graph drawing systems continue to be a popular method for visualizing graphs, but these systems typically use more complicated systems of forces that combine attractive forces on graph edges (as in Tutte's embedding) with repulsive forces between arbitrary pairs of vertices.

These additional forces may cause the system to have many locally stable configurations rather than, as in Tutte's embedding, a single global solution.