Steinitz's theorem
It can be proven by mathematical induction (as Steinitz did), by finding the minimum-energy state of a two-dimensional spring system and lifting the result into three dimensions, or by using the circle packing theorem.
By Fáry's theorem, every planar drawing can be straightened so that the curves representing the edges are line segments.
Steinitz's theorem states that these two conditions are both necessary and sufficient to characterize the skeletons of three-dimensional convex polyhedra: a given graph
As shown in the illustration, planarity can be shown by using a Schlegel diagram: if one places a light source near one face of the polyhedron, and a plane on the other side, the shadows of the polyhedron edges will form a planar graph, embedded in such a way that the edges are straight line segments.
There are three standard approaches for this part: proofs by induction, lifting two-dimensional Tutte embeddings into three dimensions using the Maxwell–Cremona correspondence, and methods using the circle packing theorem to generate a canonical polyhedron.
[10] Epifanov's proof was complicated and non-constructive, but it was simplified by Truemper using methods based on graph minors.
[8] For these proofs, carried out using any of the ways of finding sequences of ΔY- and YΔ-transformations, there exist polyhedral graphs that require a nonlinear number of steps.
If a finite planar graph is drawn and given an equilibrium stress in such a way that all interior edges of the drawing have positive weights, and all exterior edges have negative weights, then by translating this stress into a three-dimensional surface in this way, and then replacing the flat surface representing the exterior of the graph by its complement in the same plane, one obtains a convex polyhedron, with the additional property that its perpendicular projection onto the plane has no crossings.
Tutte's method begins by fixing one face of a polyhedral graph into convex position in the plane.
Then as Tutte showed, this system of equations will have a unique solution in which each face of the graph is drawn as a convex polygon.
[17] Intuitively, this solution describes the pattern that would be obtained by replacing the interior edges of the graph by ideal springs and letting them settle to their minimum-energy state.
From any such representation on a sphere, embedded into three-dimensional Euclidean space, one can form a convex polyhedron that is combinatorially equivalent to the given graph, as an intersection of half-spaces whose boundaries pass through the face circles.
[22] It is possible to prove a stronger form of Steinitz's theorem, that any polyhedral graph can be realized by a convex polyhedron whose coordinates are integers.
However, the integers that would result from Steinitz's construction are doubly exponential in the number of vertices of the given polyhedral graph.
[19] Geometrically, this means that some features of the polyhedron may have size doubly exponentially larger than others, making the realizations derived from this method problematic for applications in graph drawing.
[4] Subsequent researchers have found lifting-based realization algorithms that use only a linear number of bits per vertex.
and the other two coordinates are real numbers in the unit interval, so that each edge has length at least one while the overall polyhedron has linear volume.
Polyhedral surfaces with equal-slope faces over any base polygon (not necessarily convex) can be constructed from the polygon's straight skeleton, and an equivalent way of describing this realization is that the two-dimensional projection of the tree onto the base face forms its straight skeleton.
However, the planar graph drawings produced by Tutte's method do not necessarily lift to convex polyhedra.
[34] Circle packing methods can also be used to characterize the graphs of polyhedra that have a circumsphere through all their vertices, or an insphere tangent to all of their faces.
In both cases, the existence of a sphere is equivalent to the solvability of a system of linear inequalities on positive real variables associated with each edge of the graph.
Although there may be exponentially many linear inequalities to satisfy, a solution (if one exists) can be found in polynomial time using the ellipsoid method.
It is unlikely to have polynomial time complexity, as it is NP-hard and more strongly complete for the existential theory of the reals, even for four-dimensional polytopes, by Richter-Gebert's universality theorem.
[40] Researchers have also found graph-theoretic characterizations of the graphs of certain special classes of three-dimensional non-convex polyhedra[37][41] and four-dimensional convex polytopes.
[44] Eberhard's theorem partially characterizes the multisets of polygons that can be combined to form the faces of a convex polyhedron.
As Lovász shows, when the graph is polyhedral, a representation of it as a polyhedron can be obtained by finding a weighted adjacency matrix of corank three, finding three vectors forming a basis for its nullspace, using the coefficients of these vectors as coordinates for the vertices of a polyhedron, and scaling these vertices appropriately.
[46] The work of Epifanov on ΔY- and YΔ-transformations, strengthening Steinitz's proof, was motivated by other problems than the characterization of polyhedra.
[11] The Maxwell-Cremona correspondence between stress diagrams and polyhedral liftings was developed in a series of papers by James Clerk Maxwell from 1864 to 1870, based on earlier work of Pierre Varignon, William Rankine, and others, and was popularized in the late 19th century by Luigi Cremona.
[47] The observation that this correspondence can be used with the Tutte embedding to prove Steinitz's theorem comes from Eades & Garvan (1995);[4] see also Richter-Gebert (1996).
[51] The problem of characterizing polyhedra with inscribed or circumscribed spheres, eventually solved using a method based on circle packing realizations, goes back to unpublished work of René Descartes circa 1630[52] and to Jakob Steiner in 1832;[35][53] the first examples of polyhedra that have no realization with a circumsphere or insphere were given by Steinitz in 1928.
