Ingraph drawing andgeometric graph theory, aTutte embedding orbarycentric embedding of asimple,3-vertex-connected,planar graph is acrossing-free straight-line embedding with the properties that the outer face is aconvex polygon and that each interiorvertex is at theaverage (or barycenter) of its neighbors' positions. If the outer polygon is fixed, this condition on the interior vertices determines their position uniquely as the solution to asystem of linear equations. Solving the equations geometrically produces aplanar embedding.Tutte's spring theorem, proven byW. T. Tutte (1963), states that this unique solution is always crossing-free, and more strongly that every face of the resulting planar embedding is convex.^[1] It is called the spring theorem because such an embedding can be found as the equilibrium position for a system ofsprings representing the edges of the graph.

LetG be the graph of a cube, and (selecting one of its quadrilateral faces as the outer face) fix the four vertices of the outer face at the four corners of aunit square, the points whosex andy coordinates are all four combinations of zero and one.Then, if the remaining four vertices are placed at the four points whosex andy coordinates are combinations of 1/3 and 2/3, as in the figure, the result will be a Tutte embedding. For, at each interior vertexv of the embedding, and for each of the two coordinates, the three neighbors ofv have coordinate values that are equal tov, smaller by 1/3, and larger by 1/3; the average of these values is the same as the coordinate value ofv itself.

The condition that a vertexv be at the average of its neighbors' positions may be expressed as twolinear equations, one for thex coordinate of v and another for they coordinate of v. For a graph withn vertices,h of which are fixed in position on the outer face, there are two equations for each interior vertex and also two unknowns (the coordinates) for each interior vertex. Therefore, this gives asystem of linear equations with 2(n − h) equations in 2(n − h) unknowns, the solution to which is a Tutte embedding. AsTutte (1963) showed, for 3-vertex-connected planar graphs, this system is non-degenerate. Therefore, it has a unique solution, and (with the outer face fixed) the graph has a unique Tutte embedding. This embedding can be found inpolynomial time by solving the system of equations, for instance by usingGaussian elimination.^[2]

BySteinitz's theorem, the 3-connected planar graphs to which Tutte's spring theorem applies coincide with thepolyhedral graphs, the graphs formed by the vertices and edges of aconvex polyhedron. According to theMaxwell–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 anequilibrium 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. However, when the outer polygon is a triangle, it is possible to assign repulsive forces to its three edges to make the forces cancel there, too. In this way, Tutte embeddings can be used to findSchlegel diagrams of everyconvex polyhedron. For every 3-connected planar graphG, eitherG itself or thedual graph ofG has a triangle, so either this gives a polyhedral representation ofG or of its dual; in the case that the dual graph is the one with the triangle,polarization gives a polyhedral representation ofG itself.^[2]

In geometry processing, Tutte's embedding is used for 2Duv-parametrization${\displaystyle {\mathcal{S}}^{\ast }}$of 3D surfaces${\displaystyle \mathcal{S}}$ most commonly for the cases where the topology of the surface remains the same across${\displaystyle \mathcal{S}}$ and${\displaystyle {\mathcal{S}}^{\ast }}$(disk topology). 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. Since it is reasonable to have smaller parametrized edge lengths for the smaller edges of${\displaystyle \mathcal{S}}$, and larger parametrized edge lengths for the larger edges of${\displaystyle \mathcal{S}}$, the spring constants${\displaystyle w_{ij}}$are usually taken as the inverse of the absolute distance between the vertices${\displaystyle i,j}$ in the 3D space.

${\displaystyle \text{Distortion Energy,}E={\mathrm{\Sigma }}_{(i,j)\in E(\mathcal{S})}{w}_{ij}\Vert {\mathbf{\text{u}}}_{\text{i}}-{\mathbf{\text{u}}}_{\text{j}}{\Vert }^2\text{, where }{w}_{ij}=\frac{1}{\Vert {\mathbf{\text{v}}}_{\text{i}}-{\mathbf{\text{v}}}_{\text{j}}\Vert }\text{, }\{{\mathbf{\text{u}}}_{\text{i}}\}\in {\mathcal{S}}^{\ast }\text{, }\{{\mathbf{\text{v}}}_{\text{i}}\}\in \mathcal{S}}$

where${\displaystyle E(\mathcal{S})}$ represents the set of edges in the original 3D surface. When the weights${\displaystyle w_{ij}}$ are positive (as is the case above), it is guaranteed that the mapping is bijective without any inversions. 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-genussurfaces withnon-positive curvature, where edges are represented bygeodesics;^[3]this result was later independently rediscovered byHass & Scott (2015).^[4]Analogous results forgraphs embedded on a torus were independently provedbyDelgado-Friedrichs (2005),^[5]byGortler, Gotsman & Thurston (2006),^[6]and byLovász (2019).^[7]

Chilakamarri, Dean & Littman (1995) investigate three-dimensional graph embeddings of the graphs of four-dimensionalpolytopes, 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.Let each remaining vertex of the polytope be free to move in space, and replace each edge of the polytope by a spring. Then, find the minimum-energy configuration of the system of springs. 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 everysimple planar graph can be drawn with straight line edges is calledFáry's theorem.^[9] The Tutte spring theorem proves this for 3-connected planar graphs, but the result is true more generally for planar graphs regardless of connectivity. Using the Tutte spring system for a graph that is not 3-connected may result in degeneracies, in which subgraphs of the given graph collapse onto a point or a line segment; however, an arbitrary planar graph may be drawn using the Tutte embedding by adding extra edges to make it 3-connected, drawing the resulting 3-connected graph, and then removing the extra edges.

A graph isk-vertex-connected, but not necessarily planar, if and only if it has aconvex embedding into (k −1)-dimensional space in which an arbitraryk-tuple of vertices are placed at the vertices of asimplex and, for each remaining vertexv, theconvex hull of the neighbors of v is full-dimensional withv in its interior. If such an embedding exists, one can be found by fixing the locations of the chosenk vertices and solving a system of equations that places each vertex at the average of its neighbors, just as in Tutte's planar embedding.^[10]

Infinite elementmesh generation,Laplacian smoothing is a common method for postprocessing a generated mesh to improve the quality of its elements;^[11] it is particularly popular forquadrilateral meshes, for which other methods such asLloyd's algorithm for triangular mesh smoothing are less applicable. 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.^[12]

• Planar graphs
• Graph drawing

• Articles with short description
• Short description matches Wikidata