Steinitz's theorem
Encyclopedia
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 graph
s. 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 graph
s. Steinitz's theorem is named after Ernst Steinitz
, who proved it in 1922. Branko Grünbaum
has called this theorem “the most important and deepest known result on 3-polytopes.”
The name "Steinitz's theorem" has also been applied to other results of Steinitz:
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 segment
s. 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.
The other, more difficult, direction of Steinitz's theorem states that every planar 3-connected graph is the graph of a convex polyhedron.
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 [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).
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 nonseparating 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.
Polyhedral combinatorics
Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher dimensional convex polytopes....
, 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 graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s. 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 graph
Polyhedral graph
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...
s. Steinitz's theorem is named after Ernst Steinitz
Ernst Steinitz
Ernst Steinitz was a German mathematician.- Biography :Steinitz was born in Laurahütte , Silesia, Germany , the son of Sigismund Steinitz, a Jewish coal merchant, and his wife Auguste Cohen; he had two brothers. He studied at the University of Breslau and the University of Berlin, receiving his Ph.D...
, who proved it in 1922. Branko Grünbaum
Branko Grünbaum
Branko Grünbaum is a Croatian-born mathematician and a professor emeritus at the University of Washington in Seattle. He received his Ph.D. in 1957 from Hebrew University of Jerusalem in Israel....
has called this theorem “the most important and deepest known result on 3-polytopes.”
The name "Steinitz's theorem" has also been applied to other results of Steinitz:
- the Steinitz exchange lemmaSteinitz exchange lemmaThe Steinitz exchange lemma is a basic theorem in linear algebra used, for example, to show that any two bases for a finite-dimensional vector space have the same number of elements. The result is named after the German mathematician Ernst Steinitz...
implying that each basis of a vector spaceVector spaceA vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
has the same number of vectors, - the theorem that if the convex hullConvex hullIn mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
of a point set contains a unit sphere, then the convex hull of a finite subset of the point contains a smaller concentric sphere, and - Steinitz's vectorial generalization of the Riemann series theorem on the rearrangements of conditionally convergent series.
Definitions and statement of the theorem
An undirected graph is a system of verticesVertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
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
Vertex (geometry)
In geometry, a vertex is a special kind of point that describes the corners or intersections of geometric shapes.-Of an angle:...
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
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
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
Fáry's theorem
In mathematics, Fáry's theorem states that any simple planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be drawn...
, it is sufficient to consider only planar drawings in which the curves representing the edges are line segment
Line segment
In geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...
s. 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
Balinski's theorem
In polyhedral combinatorics, a branch of mathematics, Balinski's theorem is a statement about the graph-theoretic structure of three-dimensional polyhedra and higher-dimensional polytopes...
that the graph of any k-dimensional convex polytope
Convex polytope
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set of points in the n-dimensional space Rn...
is k-connected.
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. However, subsequent researchers have found graph drawingGraph drawing
Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...
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 [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).
In any polyhedron that represents a given polyhedral graph G, the faces of G are exactly the cycles
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
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 nonseparating cycle C is chosen, and its vertices are placed in correspondence with the vertices of a two-dimensional convex polygon
Convex polygon
In geometry, a polygon can be either convex or concave .- Convex polygons :A convex polygon is a simple polygon whose interior is a convex set...
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
Silhouette
A silhouette is the image of a person, an object or scene consisting of the outline and a basically featureless interior, with the silhouetted object usually being black. Although the art form has been popular since the mid-18th century, the term “silhouette” was seldom used until the early decades...
of the realization under parallel projection
Parallel projection
Parallel projections have lines of projection that are parallel both in reality and in the projection plane.Parallel projection corresponds to a perspective projection with an infinite focal length , or "zoom".Within parallel projection there is an ancillary category known as "pictorials"...
.
The Koebe
Paul Koebe
Paul Koebe was a 20th-century German mathematician. His work dealt exclusively with the complex numbers, his most important results being on the uniformization of Riemann surfaces in a series of four papers in 1907–1909. He did his thesis at Berlin, where he worked under Herman Schwarz...
–Andreev–Thurston
William Thurston
William Paul Thurston is an American mathematician. He is a pioneer in the field of low-dimensional topology. In 1982, he was awarded the Fields Medal for his contributions to the study of 3-manifolds...
circle packing theorem
Circle packing theorem
The circle packing theorem describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles whose interiors are disjoint...
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
Unit sphere
In mathematics, a unit sphere is the set of points of distance 1 from a fixed central point, where a generalized concept of distance may be used; a closed unit ball is the set of points of distance less than or equal to 1 from a fixed central point...
. More generally, if G is a polyhedral graph and K is any smooth three-dimensional convex body
Convex body
In mathematics, a convex body in n-dimensional Euclidean space Rn is a compact convex set with non-empty interior.A convex body K is called symmetric if it is centrally symmetric with respect to the origin, i.e. a point x lies in K if and only if its antipode, −x, also lies in K...
, 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
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
, determine whether it is the face lattice of a convex polytope
Convex polytope
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set of points in the n-dimensional space Rn...
) is complete
Complete (complexity)
In computational complexity theory, a computational problem is complete for a complexity class if it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class...
for the existential theory of the reals
Existential theory of the reals
In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form...
by Richter-Gebert's universality theorem.