Steinitz's theorem

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.[1]

This result provides a classification theorem for the three-dimensional convex polyhedra, something that is not known in higher dimensions.[2] It provides a complete and purely combinatorial description of the graphs of these polyhedra, allowing other results on them, such as Eberhard's theorem on the realization of polyhedra with given types of faces, to be proven more easily, without reference to the geometry of these shapes.[3] Additionally, it has been applied in graph drawing, as a way to construct three-dimensional visualizations of abstract graphs.[4] Branko Grünbaum has called this theorem "the most important and deepest known result on 3-polytopes."[5]

The theorem appears in a 1922 publication of Ernst Steinitz,[6] after whom it is named. 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. Several extensions of the theorem are known, in which the polyhedron that realizes a given graph has additional constraints; for instance, every polyhedral graph is the graph of a convex polyhedron with integer coordinates, or the graph of a convex polyhedron all of whose edges are tangent to a common midsphere.

Illuminating the skeleton of a convex polyhedron from a light source close to one of its faces causes its shadows to form a planar Schlegel diagram.

An undirected graph is a system of vertices and edges, each edge connecting two of the vertices. From any polyhedron one can form a graph, by letting the vertices of the graph correspond to the vertices of the polyhedron and by connecting any two graph vertices by an edge whenever the corresponding two polyhedron vertices are the endpoints of an edge of the polyhedron. This graph is known as the skeleton of the polyhedron.[7]

Illustration of the proof of Balinski's theorem, showing the zero set of a linear function (blue) passing through two given vertices (yellow) and the simplex-method paths connecting the remaining graph (green)

The other, more difficult, direction of Steinitz's theorem states that every planar 3-connected graph is the graph of a convex polyhedron. 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.

A frustum lifting the stressed drawing (with the same 2d positions) into 3d

If a graph is drawn in the plane with straight line edges, then an equilibrium stress is defined as an assignment of nonzero real numbers (weights) to the edges, with the property that each vertex is in the position given by the weighted average of its neighbors. According to the Maxwell–Cremona correspondence, an equilibrium stress can be lifted to a piecewise linear continuous three-dimensional surface such that the edges forming the boundaries between the flat parts of the surface project to the given drawing. The weight and length of each edge determines the difference in slopes of the surface on either side of the edge, and the condition that each vertex is in equilibrium with its neighbors is equivalent to the condition that these slope differences cause the surface to meet up with itself correctly in the neighborhood of the vertex. Positive weights translate to convex dihedral angles between two faces of the piecewise linear surface, and negative weights translate to concave dihedral angles. Conversely, every continuous piecewise-linear surface comes from an equilibrium stress in this way. 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.[14][15]

The Maxwell–Cremona correspondence has been used to obtain polyhedral realizations of polyhedral graphs by combining it with a planar graph drawing method of W. T. Tutte, the Tutte embedding. Tutte's method begins by fixing one face of a polyhedral graph into convex position in the plane. This face will become the outer face of a drawing of a graph. The method continues by setting up a system of linear equations in the vertex coordinates, according to which each remaining vertex should be placed at the average of its neighbors. 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.[16] 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.[17] The result is almost an equilibrium stress: if one assigns weight one to each interior edge, then each interior vertex of the drawing is in equilibrium. However, it is not always possible to assign negative numbers to the exterior edges so that they, too, are in equilibrium. Such an assignment is always possible when the outer face is a triangle, and so this method can be used to realize any polyhedral graph that has a triangular face. If a polyhedral graph does not contain a triangular face, its dual graph does contain a triangle and is also polyhedral, so one can realize the dual in this way and then realize the original graph as the polar polyhedron of the dual realization.[4][18] An alternative method for realizing polyhedra using liftings avoids duality by choosing any face with at most five vertices as the outer face. Every polyhedral graph has such a face, and by choosing the fixed shape of this face more carefully, the Tutte embedding of the rest of the graph can be lifted.[19]

A polyhedron realized from a circle packing on the blue midsphere. Each polyhedron vertex is represented in the packing by its horizon circle (red). Each face is represented by the circle made by its intersection with the sphere.

According to one variant of the circle packing theorem, for every polyhedral graph, there exists a system of circles in the plane or on any sphere, representing the vertices and faces of the graph, so that:

The same system of circles forms a representation of the dual graph by swapping the roles of circles that represent vertices, and circles that represent faces. 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. From each vertex of this polyhedron, the horizon on the sphere, seen from that vertex, is the circle that represents it. This horizon property determines the three-dimensional position of each vertex, and the polyhedron can be equivalently defined as the convex hull of the vertices, positioned in this way. The sphere becomes the midsphere of the realization: each edge of the polyhedron is tangent to the sphere, at a point where two tangent vertex circles cross two tangent face circles.[21]

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.[22] For instance, Steinitz's original induction-based proof can be strengthened in this way. However, the integers that would result from Steinitz's construction are doubly exponential in the number of vertices of the given polyhedral graph. Writing down numbers of this magnitude in binary notation would require an exponential number of bits.[18] 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]

Another way of stating the existence of integer realizations is that every three-dimensional convex polyhedron has a combinatorially equivalent integer polyhedron.[22] For instance, the regular dodecahedron is not itself an integer polyhedron, because of its regular pentagon faces, but it can be realized as an equivalent integer pyritohedron.[19] This is not always possible in higher dimensions, where there exist polytopes (such as the ones constructed from the Perles configuration) that have no integer equivalent.[27]

A Halin graph is a special case of a polyhedral graph, formed from a planar-embedded tree (with no degree-two vertices) by connecting the leaves of the tree into a cycle. For Halin graphs, one can choose polyhedral realizations of a special type: the outer cycle forms a horizontal convex base face, and every other face lies directly above the base face (as in the polyhedra realized through lifting), with all of these upper faces having the same slope. 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. The proof of this result uses induction: any rooted tree may reduced to a smaller tree by removing the leaves from an internal node whose children are all leaves, the Halin graph formed from the smaller tree has a realization by the induction hypothesis, and it is possible to modify this realization in order to add any number of leaf children to the tree node whose children were removed.[28]

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. (The polyhedra with a circumsphere are also significant in hyperbolic geometry as the ideal polyhedra.) 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. In the case of the insphere, these variables must sum to exactly one on each face cycle of the graph, and to more than one on each non-face cycle. Dually, for the circumsphere, the variables must sum to one at each vertex, and more than one across each cut with two or more vertices on each side of the cut. 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. The values of the variables from a solution determine the angles between pairs of circles in a circle packing whose corresponding polyhedron has the desired relation to its sphere.[34][35]

In any dimension higher than three, the algorithmic Steinitz problem consists of determining whether a given lattice is the face lattice of a convex polytope. 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.[37] Here, the existential theory of the reals is a class of computational problems that can be formulated in terms of finding real variables that satisfy a given system of polynomial equations and inequalities. For the algorithmic Steinitz problem, the variables of such a problem can be the vertex coordinates of a polytope, and the equations and inequalities can be used to specify the flatness of each face in the given face lattice and the convexity of each angle between faces. Completeness means that every other problem in this class can be transformed into an equivalent instance of the algorithmic Steinitz problem, in polynomial time. The existence of such a transformation implies that, if the algorithmic Steinitz problem has a polynomial time solution, then so does every problem in the existential theory of the reals, and every problem in NP.[38] However, because a given graph may correspond to more than one face lattice, it is difficult to extend this completeness result to the problem of recognizing the graphs of 4-polytopes. Determining the computational complexity of this graph recognition problem remains open.[39]

Eberhard's theorem partially characterizes the multisets of polygons that can be combined to form the faces of a convex polyhedron. It can be proven by forming a 3-connected planar graph with the given set of polygon faces, and then applying Steinitz's theorem to find a polyhedral realization of that graph.[3]

The history of Steinitz's theorem is described by Grünbaum (2007),[45] who notes its first appearance in a cryptic form in a publication of Ernst Steinitz, originally written in 1916.[6] Steinitz provided more details in later lecture notes, published after his 1928 death. Although modern treatments of Steinitz's theorem state it as a graph-theoretic characterization of polyhedra, Steinitz did not use the language of graphs.[45] The graph-theoretic formulation of the theorem was introduced in the early 1960s by Branko Grünbaum and Theodore Motzkin, with its proof also converted to graph theory in Grünbaum's 1967 text Convex Polytopes.[45] The work of Epifanov on Δ-Y and Y-Δ transforms, strengthening Steinitz's proof, was motivated by other problems than the characterization of polyhedra. Truemper (1989) credits Grünbaum with observing the relevance of this work for Steinitz's theorem.[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.[46] The observation that this correspondence can be used with the Tutte embedding to prove Steinitz's theorem comes from Eades & Garvan (1995).[4]

The circle packing theorem was proved by Paul Koebe in 1936[47][48] and (independently) by E. M. Andreev in 1970;[48][49] it was popularized in the mid-1980s by William Thurston, who (despite citing Koebe and Andreev) is often credited as one of its discoverers.[48] Andreev's version of the theorem was already formulated as a Steinitz-like characterization for certain polyhedra in hyperbolic space,[49] and the use of circle packing to realize polyhedra with midspheres comes from the work of Thurston.[50] 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[51] and to Jakob Steiner in 1832;[34][52] the first examples of polyhedra that have no realization with a circumsphere or insphere were given by Steinitz in 1928.[34][53]