Steinitz's Theorem - Strengthenings and Related Results

Strengthenings and Related Results

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. The integers resulting from Steinitz' original proof are doubly exponential in the number of vertices of the given polyhedral graph; that is, writing them down would require an exponential number of bits. However, subsequent researchers have found graph drawing algorithms that use only O(n) 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(n).

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. It is possible to specify the shape of any one face of the polyhedron: if any non-separating cycle C is chosen, and its vertices are placed in correspondence with the vertices of a two-dimensional convex polygon P, then there exists a polyhedral representation of G in which the face corresponding to C is congruent to P. 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.

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. 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.

In dimensions higher than three, the algorithmic Steinitz problem (given a lattice, determine whether it is the face lattice of a convex polytope) is complete for the existential theory of the reals by Richter-Gebert's universality theorem.