In graph drawing and geometric graph theory, a Tutte embedding or barycentric embedding of a simple, 3-vertex-connected, planar graph is a crossing-free straight-line embedding with the properties that the outer face is a convex polygon and that each interior vertex is at the average (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 a system of linear equations. Solving the equations geometrically produces a planar embedding. Tutte's spring theorem, proven by W. 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. It is called the spring theorem because such an embedding can be found as the equilibrium position for a system of springs representing the edges of the graph.
Example
Let G 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 a unit square, the points whose x and y coordinates are all four combinations of zero and one. 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. For, at each interior vertex v of the embedding, and for each of the two coordinates, the three neighbors of v have coordinate values that are equal to v, smaller by 1/3, and larger by 1/3; the average of these values is the same as the coordinate value of v itself.
System of linear equations The condition that a vertex v be at the average of its neighbors' positions may be expressed as two linear equations, one for the x coordinate of v and another for the y coordinate of v. For a graph with n 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 a system of linear equations with 2(n − h) equations in 2(n − h) unknowns, the solution to which is a Tutte embedding. As Tutte (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 in polynomial time by solving the system of equations, for instance by using Gaussian elimination.
Polyhedral representation By Steinitz's theorem, the 3-connected planar graphs to which Tutte's spring theorem applies coincide with the polyhedral graphs, the graphs formed by the vertices and edges of a convex polyhedron. 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. 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 find Schlegel diagrams of every convex polyhedron. For every 3-connected planar graph G, either G itself or the dual graph of G has a triangle, so either this gives a polyhedral representation of G or of its dual; in the case that the dual graph is the one with the triangle, polarization gives a polyhedral representation of G itself.
Applications in geometry processing In geometry processing, Tutte's embedding is used for 2D uv-parametrization S ∗ {\displaystyle {\mathcal {S}}^{*}} of 3D surfaces S {\displaystyle {\mathcal {S}}} most commonly for the cases where the topology of the surface remains the same across S {\displaystyle {\mathcal {S}}} and S ∗ {\displaystyle {\mathcal {S}}^{*}} (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 S {\displaystyle {\mathcal {S}}} , and larger parametrized edge lengths for the larger edges of S {\displaystyle {\mathcal {S}}} , the spring constants w i j {\displaystyle w_{ij}} are usually taken as the inverse of the absolute distance between the vertices i , j {\displaystyle i,~j} in the 3D space.
… excerpt ends here. Continue reading the full article.
