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:
“The question of place and climate is most closely related to the question of nutrition. Nobody is free to live everywhere; and whoever has to solve great problems that challenge all his strength actually has a very restricted choice in this matter. The influence of climate on our metabolism, its retardation, its acceleration, goes so far that a mistaken choice of place and climate can not only estrange a man from his task but can actually keep it from him: he never gets to see it.”
—Friedrich Nietzsche (1844–1900)
“There is not a single rule, however plausible, and however firmly grounded in epistemology, that is not violated at some time or other. It becomes evident that such violations are not accidental events, they are not results of insufficient knowledge or of inattention which might have been avoided. On the contrary, we see that they are necessary for progress.”
—Paul Feyerabend (1924–1994)