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 (with at least four vertices).[1][2] 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.[3] Steinitz's theorem is named after Ernst Steinitz, who proved it in 1922.[4] Branko Grünbaum has called this theorem “the most important and deepest known result on 3-polytopes.”[2]

The name "Steinitz's theorem" has also been applied to other results of Steinitz:

Definitions and statement of the theorem

Illuminating the skeleton of a convex polyhedron from a light source close to one of its faces causes its shadows to form a planar Schlegel diagram.

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.

One direction of Steinitz's theorem (the easier direction to prove) states that the graph of every convex polyhedron is planar and 3-connected. As shown in the illustration, planarity can be shown by using a Schlegel diagram: if one places a light source near one face of the polyhedron, and a plane on the other side, the shadows of the polyhedron edges will form a planar graph, embedded in such a way that the edges are straight line segments. The 3-connectivity of a polyhedral graph is a special case of Balinski's theorem that the graph of any k-dimensional convex polytope is k-connected.[11]

The other, more difficult, direction of Steinitz's theorem states that every planar 3-connected graph is the graph of a convex polyhedron.

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.[12] However, subsequent researchers have found graph drawing algorithms that use only O(n) bits per vertex.[13][14] 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 [0,2n − 4] and the other two coordinates are real numbers in the range [0,1], so that each edge has length at least one while the overall polyhedron has volume O(n).[15]

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

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

In any dimension 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, as is the problem of recognizing the graphs of convex polytopes.[20]

See also

References

  1. ↑ Lectures on Polytopes, by Günter M. Ziegler (1995) ISBN 0-387-94365-X , Chapter 4 "Steinitz' Theorem for 3-Polytopes", p.103.
  2. ↑ 2.0 2.1 Branko Grünbaum, Convex Polytopes, 2nd edition, prepared by Volker Kaibel, Victor Klee, and Günter M. Ziegler, 2003, ISBN 0-387-40409-0, ISBN 978-0-387-40409-7, 466pp.
  3. ↑ Weisstein, Eric W., "Polyhedral graph", MathWorld.
  4. ↑ Steinitz, E. (1922), "Polyeder und Raumeinteilungen", Encyclopädie der mathematischen Wissenschaften, Band 3 (Geometries), pp. 1–139.
  5. ↑ Zynel, Mariusz (1996), "The Steinitz theorem and the dimension of a vector space", Formalized Mathematics 5 (8): 423–428, CiteSeerX: 10.1.1.79.1707.
  6. ↑ Kirkpatrick, David; Mishra, Bhubaneswar; Yap, Chee-Keng (1992), "Quantitative Steinitz's theorems with applications to multifingered grasping", Discrete & Computational Geometry 7 (1): 295–318, doi:10.1007/BF02187843.
  7. ↑ Rosenthal, Peter (1987), "The remarkable theorem of Lévy and Steinitz", American Mathematical Monthly 94 (4): 342–351, JSTOR 2323094.
  8. ↑ Banaszczyk, Wojciech (1991). "Chapter 3.10 The Lévy-Steinitz theorem". Additive subgroups of topological vector spaces. Lecture Notes inMathematics 1466. Berlin: Springer-Verlag. pp. viii+178. ISBN 3-540-53917-4. MR 1119302.
  9. ↑ Kadets, V. M.; Kadets, M. I. (1991). "Chapter 6 The Steinitz theorem and B-convexity". Rearrangements of series in Banach spaces. Translations of Mathematical Monographs 86 (Translated by Harold H. McFaden from the Russian-language (Tartu) 1988 ed.). Providence, RI: American Mathematical Society. pp. iv+123. ISBN 0-8218-4546-2. MR 1108619.
  10. ↑ Kadets, Mikhail I.; Kadets, Vladimir M. (1997). "Chapter 2.1 Steinitz's theorem on the sum range of a series, Chapter 7 The Steinitz theorem and B-convexity". Series in Banach spaces: Conditional and unconditional convergence. Operator Theory: Advances and Applications 94 (Translated by Andrei Iacob from the Russian-language ed.). Basel: Birkhäuser Verlag. pp. viii+156. ISBN 3-7643-5401-1. MR 1442255.
  11. ↑ Balinski, M. L. (1961), "On the graph structure of convex polyhedra in n-space", Pacific Journal of Mathematics 11 (2): 431–434, doi:10.2140/pjm.1961.11.431, MR 0126765.
  12. ↑ Venkatasubramanian, Suresh (2006), Planar graphs and Steinitz's theorem.
  13. ↑ Ribó Mor, Ares; Rote, Günter; Schulz, André (2011), "Small Grid Embeddings of 3-Polytopes", Discrete & Computational Geometry 45 (1): 65–87, doi:10.1007/s00454-010-9301-0.
  14. ↑ Buchin, Kevin; Schulz, André (2010), "On the number of spanning trees a planar graph can have", Algorithms - 18th Annual European Symposium (ESA 2010), Lecture Notes in Computer Science 6346, Springer-Verlag, pp. 110–121, doi:10.1007/978-3-642-15775-2.
  15. ↑ Schulz, André (2011), "Drawing 3-polytopes with good vertex resolution", Journal of Graph Algorithms and Applications 15 (1): 33–52, doi:10.7155/jgaa.00216.
  16. ↑ Barnette, David; Grünbaum, Branko (1970), "Preassigning the shape of a face", Pacific Journal of Mathematics 32 (2): 299–306, doi:10.2140/pjm.1970.32.299, MR 0259744.
  17. ↑ Barnette, David W. (1970), "Projections of 3-polytopes", Israel Journal of Mathematics 8 (3): 304–308, doi:10.1007/BF02771563.
  18. ↑ Ziegler, Günter M. (2007), "Convex polytopes: extremal constructions and f-vector shapes. Section 1.3: Steinitz's theorem via circle packings", in Miller, Ezra; Reiner, Victor; Sturmfels, Bernd, Geometric Combinatorics, IAS/Park City Mathematics Series 13, American Mathematical Society, pp. 628–642, ISBN 978-0-8218-3736-8.
  19. ↑ Schramm, Oded (1992), "How to cage an egg", Inventiones Mathematicae 107 (3): 543–560, doi:10.1007/BF01231901, MR 1150601.
  20. ↑ Richter-Gebert, Jürgen (1996). Realization Spaces of Polytopes. Lecture Notes in Mathematics 1643. Springer-Verlag. ISBN 978-3-540-62084-6.