Steinitz's theorem

Δ-Y and Y-Δ transforms of a polyhedron

Although Steinitz's original proof was not expressed in terms of graph theory, it can be rewritten in those terms, and involves finding a sequence of Δ-Y and Y-Δ transforms that reduce any 3-connected planar graph to ${\displaystyle K_{4}}$, 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 and converted into geometric operations that build up the desired polyhedron step by step starting from a tetrahedron. Each Y-Δ transform in the reversed sequence can be performed geometrically by slicing off a degree-three vertex from a polyhedron. A Δ-Y transform in the reversed sequence can be performed geometrically 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 far side of the removed face from the polyhedron. When the triple intersection point is not on the far side of this face, 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 ${\displaystyle K_{4}}$, every polyhedral graph can be realized as a polyhedron.[5]

A later work by Epifanov strengthened Steinitz's proof that every polyhedral graph can be reduced to ${\displaystyle K_{4}}$ 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.[10] 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.[11] This idea can be used to replace Steinitz's lemma that a reduction sequence exists. After this replacement, the rest of the proof can be carried out using induction in the same way as Steinitz's original proof.[8] For these proofs, carried out using any of the ways of finding sequences of Δ-Y and Y-Δ transforms, there exist polyhedral graphs that require a nonlinear number of steps. More precisely, every planar graph can be reduced using a number of steps at most proportional to ${\displaystyle n^{3/2}}$, and infinitely many graphs require a number of steps at least proportional to ${\displaystyle n^{3/2}}$, where ${\displaystyle n}$ is the number of vertices in the graph.[12][13]

An alternative form of induction proof is based on removing edges (and compressing out the degree-two vertices that might be left after this removal) or contracting edges and forming a minor of the given planar graph. Any polyhedral graph can be reduced to ${\displaystyle K_{4}}$ 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.[14]

Equilibrium stress on the graph of a cube

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.[15][16]

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.[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.[18] 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][19] 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.[20]

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:

• each two adjacent vertices of the graph are represented by tangent circles,
• each two adjacent faces of the graph are represented by tangent circle,
• each pair of a vertex and a face that it touches are represented by circles that cross at a right angle, and
• all other pairs of circles are separated from each other.[21]

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.[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.[23] 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.[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.[20][24] It is also possible to relax the requirement that the coordinates be integers, and assign coordinates in such a way that the ${\displaystyle x}$-coordinates of the vertices are distinct integers in the range from 0 to ${\displaystyle 2n-4}$ 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.[25][26] Some polyhedral graphs are known to be realizable on grids of only polynomial size; in particular this is true for the pyramids (realizations of wheel graphs), prisms (realizations of prism graphs), and stacked polyhedra (realizations of Apollonian networks).[27]

Another way of stating the existence of integer realizations is that every three-dimensional convex polyhedron has a combinatorially equivalent integer polyhedron.[23] 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.[20] 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.[28]

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.[29]

In any polyhedron that represents a given polyhedral graph ${\displaystyle G}$, the faces of ${\displaystyle G}$ are exactly the cycles in ${\displaystyle G}$ that do not separate ${\displaystyle G}$ into two components: that is, removing a facial cycle from ${\displaystyle G}$ leaves the rest of ${\displaystyle G}$ as a connected subgraph. Such cycles are called peripheral cycles. Thus, the combinatorial structure of the faces (but not their geometric shapes) is 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.[30] It is also always possible, given a polyhedral graph ${\displaystyle G}$ and an arbitrary cycle ${\displaystyle C}$ in ${\displaystyle G}$, to find a realization for which ${\displaystyle C}$ forms the silhouette of the realization under parallel projection.[31]

The realization of polyhedra using the circle packing theorem provides another strengthening of Steinitz's theorem: 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, the midsphere of the polyhedron.[22] 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.[32][33] More generally, if ${\displaystyle G}$ is a polyhedral graph and ${\displaystyle K}$ is any smooth three-dimensional convex body, it is possible to find a polyhedral representation of ${\displaystyle G}$ in which all edges are tangent to ${\displaystyle K}$.[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. (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.[35][36]