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.
Read more about this topic: Steinitz's Theorem
Famous quotes containing the words related and/or results:
“A parent who from his own childhood experience is convinced of the value of fairy tales will have no difficulty in answering his child’s questions; but an adult who thinks these tales are only a bunch of lies had better not try telling them; he won’t be able to related them in a way which would enrich the child’s life.”
—Bruno Bettelheim (20th century)
“I have no doubt that it was a principle they fought for, as much as our ancestors, and not to avoid a three-penny tax on their tea; and the results of this battle will be as important and memorable to those whom it concerns as those of the battle of Bunker Hill, at least.”
—Henry David Thoreau (1817–1862)