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. Branko Grünbaum has called this theorem “the most important and deepest known result on 3-polytopes.”
The theorem appears in a 1922 paper of Ernst Steinitz, after whom it is named. It can be proven by mathematical induction, 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.
In higher dimensions, the problem of characterizing the graphs of convex polytopes remains open.
Definitions and statement of the theorem
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.A graph is planar if it can be drawn with its vertices as points in the Euclidean plane, and its edges as curves that connect these points, such that no two edge curves cross each other and such that the point representing a vertex lies on the curve representing an edge only when the vertex is an endpoint of the edge. By Fáry's theorem, it is sufficient to consider only planar drawings in which the curves representing the edges are line segments. A graph is 3-connected if, after the removal of any two of its vertices, any other pair of vertices remain connected by a path.
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 is the graph of a convex three-dimensional polyhedron, if and only if is planar and 3-vertex-connected.
History and naming
Steinitz's theorem is named after Ernst Steinitz, who submitted its first proof for publication in 1916.The name "Steinitz's theorem" has also been applied to other results of Steinitz:
- the Steinitz exchange lemma implying that each basis of a vector space has the same number of vectors,
- the theorem that if the convex hull of a point set contains a unit sphere, then the convex hull of a finite subset of the point contains a smaller concentric sphere, and
- Steinitz's vectorial generalization of the Riemann series theorem on the rearrangements of conditionally convergent series.
Proofs
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.
Induction
Steinitz' original proof involved finding a sequence of Δ-Y and Y-Δ transforms that reduce any 3-connected planar graph to K4, the graph of the tetrahedron. A Y-Δ transform removes a degree-three vertex from a graph, adding edges between all of its former neighbors if those edges did not already exist; the reverse transformation, a Δ-Y transform, removes the edges of a triangle from a graph and replaces them by a new degree-three vertex adjacent to the same three vertices. Once such a sequence is found, it can be reversed to give a sequence of Δ-Y and Y-Δ transforms that build up the desired polyhedron step by step starting from a polyhedron. Each Y-Δ transform in this sequence can be performed by slicing off a degree-three vertex from a polyhedron. A Δ-Y transform can be performed by removing a triangular face from a polyhedron and extending its neighboring faces until the point where they meet, but only when that triple intersection point of the three neighboring faces is on the correct side of the polyhedron; when the triple intersection point is not on the correct side, a projective transformation of the polyhedron suffices to move it to the correct side. Therefore, by induction on the number of Δ-Y and Y-Δ transforms needed to reduce a given graph to K4, every polyhedral graph can be realized as a polyhedron.A later work by Epifanov strengthened Steinitz's proof that every polyhedral graph can be reduced to K4 by Δ-Y and Y-Δ transforms. Epifanov proved that if two vertices are specified in a planar graph, then the graph can be reduced to a single edge between those terminals by combining Δ-Y and Y-Δ transforms with series-parallel reductions. Epifanov's proof was complicated and non-constructive, but it was simplified by Truemper using methods based on graph minors. Truemper observed that every grid graph is reducible by Δ-Y and Y-Δ transforms in this way, that this reducibility is preserved by graph minors, and that every planar graph is a minor of a grid graph. This idea can be used to replace Steinitz's lemma that a reduction sequence exists, in a proof of Steinitz's theorem using induction in the same way. However, there exist graphs that require a nonlinear number of steps in any sequence of Δ-Y and Y-Δ transforms. More precisely, Ω steps are sometimes necessary, and the best known upper bound on the number of steps is even worse, O.
An alternative form of induction proof is based on removing edges or contracting edges and forming a minor of the given planar graph. Any polyhedral graph can be reduced to K4 by a linear number of these operations, and again the operations can be reversed and the reversed operations performed geometrically, giving a polyhedral realization of the graph. However, while it is simpler to prove that a reduction sequence exists for this type of argument, and the reduction sequences are shorter, the geometric steps needed to reverse the sequence are more complicated.
Lifting
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 to the edges, with the property that each vertex is in the position given by the weighted sum 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.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. 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. It is also possible to realize any polyhedral graph directly by choosing the outer face to be any face with at most five vertices and choosing more carefully the fixed shape of this face in such a way that the Tutte embedding can be lifted, or by using an incremental method instead of Tutte's method to find a liftable planar drawing that does not have equal weights for all the interior edges.
Circle packing
According to one variant of the circle packing theorem, for every polyhedral graph and its dual graph, there exists a system of circles in the plane or on any sphere,representing the vertices of both graphs, so that two adjacent vertices in the same graph are represented by tangent circles, a primal and dual vertex that represent a vertex and face that touch each other are represented by orthogonal circles, and all remaining pairs of circles are disjoint. From such a representation on a sphere, one can find a polyhedral realization of the given graph as the intersection of a collection of halfspaces, one for each circle that represents a dual vertex, with the boundary of the halfspace containing the circle. Alternatively and equivalently, one can find the same polyhedron as the convex hull of a collection of points, such that the horizon seen when viewing the sphere from any vertex equals the circle that corresponds to that vertex. The sphere becomes the midsphere of the realization: each edge of the polyhedron is tangent to it, at the point where two tangent primal circles and two dual circles orthogonal to the primal circles and tangent to each other all meet.
Realizations with additional properties
Integer coordinates
It is possible to prove a stronger form of Steinitz's theorem, that any polyhedral graph can be realized by a convex polyhedron for which all of the vertex coordinates are integers. For instance,Steinitz's original induction-based proof can be strengthened in this way. However, the integers that would result from this 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.
Subsequent researchers have found lifting-based realization algorithms that use only O bits per vertex. It is also possible to relax the requirement that the coordinates be integers, and assign coordinates in such a way that the x-coordinates of the vertices are distinct integers in the range and the other two coordinates are real numbers in the range , so that each edge has length at least one while the overall polyhedron has volume O. Some polyhedral graphs are known to be realizable on grids of only polynomial size; in particular this is true for the pyramids, prisms, and stacked polyhedra.
Equal slopes
A Halin graph is a planar graph formed from a planar-embedded tree by connecting the leaves of the tree into a cycle. Every Halin graph can be realized by a polyhedron in which this cycle forms a horizontal base face, every other face lies directly above the base face, and every face has the same slope. Equivalently, the straight skeleton of the base face is combinatorially equivalent to the tree from which the Halin graph was formed. 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.Specifying the shape of a face
In any polyhedron that represents a given polyhedral graph G, the faces of G are exactly the cycles in G that do not separate G into two components: that is, removing a facial cycle from G leaves the rest of G as a connected subgraph. Thus, the faces are uniquely determined from the graph structure.Another strengthening of Steinitz's theorem, by Barnette and Grünbaum, states that for any polyhedral graph, any face of the graph, and any convex polygon representing that face, it is possible to find a polyhedral realization of the whole graph that has the specified shape for the designated face. This is related to a theorem of Tutte, that any polyhedral graph can be drawn in the plane with all faces convex and any specified shape for its outer face. However, the planar graph drawings produced by Tutte's method do not necessarily lift to convex polyhedra. Instead, Barnette and Grünbaum prove this result using an inductive method It is also always possible, given a polyhedral graph G and an arbitrary cycle C, to find a realization such that C forms the silhouette of the realization under parallel projection.
Tangent spheres
The Koebe–Andreev–Thurston circle packing theorem can be interpreted as providing another strengthening of Steinitz's theorem, that every 3-connected planar graph may be represented as a convex polyhedron in such a way that all of its edges are tangent to the same unit sphere. By performing a carefully chosen Möbius transformation of a circle packing before transforming it into a polyhedron, it is possible to find a polyhedral realization that realizes all the symmetries of the underlying graph, in the sense that every graph automorphism is a symmetry of the polyhedral realization. More generally, if G is a polyhedral graph and K is any smooth three-dimensional convex body, it is possible to find a polyhedral representation of G in which all edges are tangent to K.Circle packing methods can also be used to characterize the graphs of polyhedra that have a circumsphere or insphere. The characterization involves edge weights, constrained by systems of linear inequalities. These weights correspond to the angles made by adjacent circles in a system of circles, made by the intersections of the faces of the polyhedron with their circumsphere or the horizons of the vertices of the polyhedron on its insphere.
Related results
In any dimension higher than three, the algorithmic Steinitz problem is complete for the existential theory of the reals by Richter-Gebert's universality theorem. 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, and this problem's complexity remains open.Researchers have also found graph-theoretic characterizations of the graphs of certain special classes of three-dimensional non-convex polyhedra and four-dimensional convex polytopes. However, in both cases, the general problem remains unsolved. Indeed, even the problem of determining which complete graphs are the graphs of non-convex polyhedra remains unsolved.
László Lovász has shown a correspondence between polyhedral representations of graphs and matrices realizing the Colin de Verdière graph invariants of the same graphs.