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. Research in polyhedral c ...

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

convex polyhedra A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wor ...

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. In other words, it can be drawn in such a way that no edges cro ...

polyhedral graph In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-c ...

classification theorem In mathematics, a classification theorem answers the classification problem "What are the objects of a given type, up to some equivalence?". It gives a non-redundant enumeration: each object is equivalent to exactly one class. A few issues relat ...

graph 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, car ...

Branko Grünbaum Branko Grünbaum ( he, ברנקו גרונבאום; 2 October 1929 – 14 September 2018) was a Croatian-born mathematician of Jewish descent3-polytopes." The theorem appears in a 1922 publication of Ernst Steinitz, after whom it is named. It can be proven by

mathematical induction Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ... all hold. Informal metaphors help ...

(as Steinitz did), by finding the minimum-energy state of a two-dimensional spring system and lifting the result into three dimensions, or by using the

circle packing theorem The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles (in gen ...

. Several extensions of the theorem are known, in which the polyhedron that realizes a given graph has additional constraints; for instance, every polyhedral graph is the graph of a convex polyhedron with integer coordinates, or the graph of a convex polyhedron all of whose edges are tangent to a common

midsphere In geometry, the midsphere or intersphere of a polyhedron is a sphere which is tangent to every edge of the polyhedron. That is to say, it touches any given edge at exactly one point. Not every polyhedron has a midsphere, but for every convex ...

.

Definitions and statement of the theorem

An

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

is a system of vertices and edges, each edge connecting two of the vertices. As is common in graph theory, for the purposes of Steinitz's theorem these graphs are restricted to being finite (the vertices and edges are

finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. ...

s) and simple (no two edges connect the same two vertices, and no edge connects a vertex to itself). 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 A skeleton is the structural frame that supports the body of an animal. There are several types of skeletons, including the exoskeleton, which is the stable outer shell of an organism, the endoskeleton, which forms the support structure inside ...

of the polyhedron.More technically, this graph is the 1-skeleton; see , p. 138, and , p. 64. A graph is planar if it can be drawn with its vertices as points in the

Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions ...

, 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, every planar drawing can be straightened so that the curves representing the edges are

line segment In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between ...

s. A graph is 3-connected if it has more than three vertices and, after the removal of any two of its vertices, any other pair of vertices remain connected by a path. Steinitz's theorem states that these two conditions are both

necessary and sufficient In logic and mathematics, necessity and sufficiency are terms used to describe a conditional or implicational relationship between two statements. For example, in the conditional statement: "If then ", is necessary for , because the truth of ...

to characterize the skeletons of three-dimensional convex polyhedra: a given graph

G

is the graph of a convex three-dimensional polyhedron, if and only if

G

is planar and 3-vertex-connected.

Proofs

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 In geometry, a Schlegel diagram is a projection of a polytope from \mathbb^d into \mathbb^ through a point just outside one of its facets. The resulting entity is a polytopal subdivision of the facet in \mathbb^ that, together with the ori ...

: 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 connectivity of the graph of a polytope, after removing any

k-1

of its vertices, can be proven by choosing one more vertex

v

, finding a

linear function In mathematics, the term linear function refers to two distinct but related notions: * In calculus and related areas, a linear function is a function whose graph is a straight line, that is, a polynomial function of degree zero or one. For di ...

that is zero on the resulting set of

k

vertices, and following the paths generated by the

simplex method In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are no ...

to connect every vertex to one of two extreme vertices of the linear function, with the chosen vertex

v

connected to both. The other, more difficult, direction of Steinitz's theorem states that every planar 3-connected graph is the graph of a convex polyhedron. There are three standard approaches for this part: proofs by induction, lifting two-dimensional Tutte embeddings into three dimensions using the Maxwell–Cremona correspondence, and methods using the

circle packing theorem The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles (in gen ...

to generate a

canonical polyhedron In geometry, the midsphere or intersphere of a polyhedron is a sphere which is tangent to every edge of the polyhedron. That is to say, it touches any given edge at exactly one point. Not every polyhedron has a midsphere, but for every convex ...

.

Induction

Although Steinitz's original proof was not expressed in terms of graph theory, it can be rewritten in those terms, and involves finding a sequence of Δ-Y and Y-Δ transforms that reduce any 3-connected planar graph to

K_4

, the graph of the tetrahedron. A Y-Δ transform removes a degree-three vertex from a graph, adding edges between all of its former neighbors if those edges did not already exist; the reverse transformation, a Δ-Y transform, removes the edges of a triangle from a graph and replaces them by a new degree-three vertex adjacent to the same three vertices. Once such a sequence is found, it can be reversed and converted into geometric operations that build up the desired polyhedron step by step starting from a tetrahedron. Each Y-Δ transform in the reversed sequence can be performed geometrically by slicing off a degree-three vertex from a polyhedron. A Δ-Y transform in the reversed sequence can be performed geometrically by removing a triangular face from a polyhedron and extending its neighboring faces until the point where they meet, but only when that triple intersection point of the three neighboring faces is on the far side of the removed face from the polyhedron. When the triple intersection point is not on the far side of this face, a

projective transformation In projective geometry, a homography is an isomorphism of projective spaces, induced by an isomorphism of the vector spaces from which the projective spaces derive. It is a bijection that maps lines to lines, and thus a collineation. In genera ...

of the polyhedron suffices to move it to the correct side. Therefore, by induction on the number of Δ-Y and Y-Δ transforms needed to reduce a given graph to

K_4

, every polyhedral graph can be realized as a polyhedron. A later work by Epifanov strengthened Steinitz's proof that every polyhedral graph can be reduced to

K_4

by Δ-Y and Y-Δ transforms. Epifanov proved that if two vertices are specified in a planar graph, then the graph can be reduced to a single edge between those terminals by combining Δ-Y and Y-Δ transforms with series–parallel reductions. Epifanov's proof was complicated and non-constructive, but it was simplified by Truemper using methods based on

graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only i ...

s. Truemper observed that every

grid graph In graph theory, a lattice graph, mesh graph, or grid graph is a graph whose drawing, embedded in some Euclidean space , forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a lat ...

is reducible by Δ-Y and Y-Δ transforms in this way, that this reducibility is preserved by graph minors, and that every planar graph is a minor of a grid graph. This idea can be used to replace Steinitz's lemma that a reduction sequence exists. After this replacement, the rest of the proof can be carried out using induction in the same way as Steinitz's original proof. For these proofs, carried out using any of the ways of finding sequences of Δ-Y and Y-Δ transforms, there exist polyhedral graphs that require a nonlinear number of steps. More precisely, infinitely many graphs require a number of steps at least proportional to

n^

, where

n

is the number of vertices in the graph, and the best known

upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an elem ...

on the number of steps that suffice is larger, proportional to

n^2

. An alternative form of induction proof is based on removing edges (and compressing out the degree-two vertices that might be left after this removal) or contracting edges and forming a minor of the given planar graph. Any polyhedral graph can be reduced to

K_4

by a linear number of these operations, and again the operations can be reversed and the reversed operations performed geometrically, giving a polyhedral realization of the graph. However, while it is simpler to prove that a reduction sequence exists for this type of argument, and the reduction sequences are shorter, the geometric steps needed to reverse the sequence are more complicated.

Lifting

If a graph is drawn in the plane with straight line edges, then an equilibrium stress is defined as an assignment of nonzero real numbers (weights) to the edges, with the property that each vertex is in the position given by the weighted average of its neighbors. According to the Maxwell–Cremona correspondence, an equilibrium stress can be lifted to a piecewise linear continuous three-dimensional surface such that the edges forming the boundaries between the flat parts of the surface project to the given drawing. The weight and length of each edge determines the difference in

slopes In mathematics, the slope or gradient of a line is a number that describes both the ''direction'' and the ''steepness'' of the line. Slope is often denoted by the letter ''m''; there is no clear answer to the question why the letter ''m'' is used ...

of the surface on either side of the edge, and the condition that each vertex is in equilibrium with its neighbors is equivalent to the condition that these slope differences cause the surface to meet up with itself correctly in the neighborhood of the vertex. Positive weights translate to convex

dihedral angle A dihedral angle is the angle between two intersecting planes or half-planes. In chemistry, it is the clockwise angle between half-planes through two sets of three atoms, having two atoms in common. In solid geometry, it is defined as the un ...

s between two faces of the piecewise linear surface, and negative weights translate to concave dihedral angles. Conversely, every continuous piecewise-linear surface comes from an equilibrium stress in this way. If a finite planar graph is drawn and given an equilibrium stress in such a way that all interior edges of the drawing have positive weights, and all exterior edges have negative weights, then by translating this stress into a three-dimensional surface in this way, and then replacing the flat surface representing the exterior of the graph by its complement in the same plane, one obtains a convex polyhedron, with the additional property that its perpendicular projection onto the plane has no crossings. The Maxwell–Cremona correspondence has been used to obtain polyhedral realizations of polyhedral graphs by combining it with a planar

graph 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, car ...

method of

W. T. Tutte William Thomas Tutte OC FRS FRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian codebreaker and mathematician. During the Second World War, he made a brilliant and fundamental advance in cryptanalysis of the Lorenz cipher, a major ...

, the Tutte embedding. Tutte's method begins by fixing one face of a polyhedral graph into convex position in the plane. This face will become the outer face of a drawing of a graph. The method continues by setting up a system of linear equations in the vertex coordinates, according to which each remaining vertex should be placed at the average of its neighbors. Then as Tutte showed, this system of equations will have a unique solution in which each face of the graph is drawn as a convex polygon. Intuitively, this solution describes the pattern that would be obtained by replacing the interior edges of the graph by ideal springs and letting them settle to their minimum-energy state. The result is almost an equilibrium stress: if one assigns weight one to each interior edge, then each interior vertex of the drawing is in equilibrium. However, it is not always possible to assign negative numbers to the exterior edges so that they, too, are in equilibrium. Such an assignment is always possible when the outer face is a triangle, and so this method can be used to realize any polyhedral graph that has a triangular face. If a polyhedral graph does not contain a triangular face, its

dual graph In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loo ...

does contain a triangle and is also polyhedral, so one can realize the dual in this way and then realize the original graph as the polar polyhedron of the dual realization. An alternative method for realizing polyhedra using liftings avoids duality by choosing any face with at most five vertices as the outer face. Every polyhedral graph has such a face, and by choosing the fixed shape of this face more carefully, the Tutte embedding of the rest of the graph can be lifted.

Circle packing

According to one variant of the

circle packing theorem The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles (in gen ...

, for every polyhedral graph, there exists a system of circles in the plane or on any sphere, representing the vertices and faces of the graph, so that: *each two adjacent vertices of the graph are represented by tangent circles, *each two adjacent faces of the graph are represented by tangent circle, *each pair of a vertex and a face that it touches are represented by circles that cross at a right angle, and *all other pairs of circles are separated from each other. The same system of circles forms a representation of the

dual graph In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loo ...

by swapping the roles of circles that represent vertices, and circles that represent faces. From any such representation on a sphere, embedded into three-dimensional Euclidean space, one can form a convex polyhedron that is combinatorially equivalent to the given graph, as an intersection of half-spaces whose boundaries pass through the face circles. From each vertex of this polyhedron, the

horizon The horizon is the apparent line that separates the surface of a celestial body from its sky when viewed from the perspective of an observer on or near the surface of the relevant body. This line divides all viewing directions based on whether ...

on the sphere, seen from that vertex, is the circle that represents it. This horizon property determines the three-dimensional position of each vertex, and the polyhedron can be equivalently defined as the convex hull of the vertices, positioned in this way. The sphere becomes the

midsphere In geometry, the midsphere or intersphere of a polyhedron is a sphere which is tangent to every edge of the polyhedron. That is to say, it touches any given edge at exactly one point. Not every polyhedron has a midsphere, but for every convex ...

of the realization: each edge of the polyhedron is tangent to the sphere, at a point where two tangent vertex circles cross two tangent face circles.

Realizations with additional properties

Integer coordinates

It is possible to prove a stronger form of Steinitz's theorem, that any polyhedral graph can be realized by a convex polyhedron whose coordinates are integers., theorem 13.2.3, p. 244, states this in an equivalent form where the coordinates are

rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ra ...

s. For instance, Steinitz's original induction-based proof can be strengthened in this way. However, the integers that would result from Steinitz's construction are doubly exponential in the number of vertices of the given polyhedral graph. Writing down numbers of this magnitude in binary notation would require an exponential number of bits. Geometrically, this means that some features of the polyhedron may have size doubly exponentially larger than others, making the realizations derived from this method problematic for applications in

graph 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, car ...

. Subsequent researchers have found lifting-based realization algorithms that use only a linear number of 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 from 0 to

2n-4

and the other two coordinates are real numbers in the

unit interval In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1. It is often denoted ' (capital letter ). In addition to its role in real analys ...

, so that each edge has length at least one while the overall polyhedron has linear volume. Some polyhedral graphs are known to be realizable on grids of only polynomial size; in particular this is true for the pyramids (realizations of

wheel graph A wheel is a circular component that is intended to rotate on an axle bearing. The wheel is one of the key components of the wheel and axle which is one of the six simple machines. Wheels, in conjunction with axles, allow heavy objects to be ...

s), prisms (realizations of prism graphs), and stacked polyhedra (realizations of Apollonian networks). Another way of stating the existence of integer realizations is that every three-dimensional convex polyhedron has a combinatorially equivalent integer polyhedron. For instance, the

regular dodecahedron A regular dodecahedron or pentagonal dodecahedron is a dodecahedron that is regular, which is composed of 12 regular pentagonal faces, three meeting at each vertex. It is one of the five Platonic solids. It has 12 faces, 20 vertices, 30 edges, ...

is not itself an integer polyhedron, because of its regular pentagon faces, but it can be realized as an equivalent integer

pyritohedron In geometry, a dodecahedron (Greek , from ''dōdeka'' "twelve" + ''hédra'' "base", "seat" or "face") or duodecahedron is any polyhedron with twelve flat faces. The most familiar dodecahedron is the regular dodecahedron with regular pentagon ...

. This is not always possible in higher dimensions, where there exist polytopes (such as the ones constructed from the

Perles configuration In geometry, the Perles configuration is a system of nine points and nine lines in the Euclidean plane for which every combinatorially equivalent realization has at least one irrational number as one of its coordinates. It can be constructed from ...

) that have no integer equivalent.

Equal slopes

A Halin graph is a special case of a polyhedral graph, formed from a planar-embedded

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

(with no degree-two vertices) by connecting the leaves of the tree into a cycle. For Halin graphs, one can choose polyhedral realizations of a special type: the outer cycle forms a horizontal convex base face, and every other face lies directly above the base face (as in the polyhedra realized through lifting), with all of these upper faces having the same slope. Polyhedral surfaces with equal-slope faces over any base polygon (not necessarily convex) can be constructed from the polygon's straight skeleton, and an equivalent way of describing this realization is that the two-dimensional projection of the tree onto the base face forms its straight skeleton. The proof of this result uses induction: any rooted tree may reduced to a smaller tree by removing the leaves from an internal node whose children are all leaves, the Halin graph formed from the smaller tree has a realization by the induction hypothesis, and it is possible to modify this realization in order to add any number of leaf children to the tree node whose children were removed.

Specifying the shape of a face

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. Such cycles are called

peripheral cycle In graph theory, a peripheral cycle (or peripheral circuit) in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles (or, as they were initially called, peripheral polygo ...

s. Thus, the combinatorial structure of the faces (but not their geometric shapes) is uniquely determined from the graph structure. Another strengthening of Steinitz's theorem, by Barnette and Grünbaum, states that for any polyhedral graph, any face of the graph, and any convex polygon representing that face, it is possible to find a polyhedral realization of the whole graph that has the specified shape for the designated face. This is related to a theorem of Tutte, that any polyhedral graph can be drawn in the plane with all faces convex and any specified shape for its outer face. However, the planar

graph 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, car ...

s produced by Tutte's method do not necessarily lift to convex polyhedra. Instead, Barnette and Grünbaum prove this result using an inductive method. It is also always possible, given a polyhedral graph

G

and an arbitrary cycle

C

in

G

, to find a realization for which

C

forms the

silhouette A silhouette ( , ) is the image of a person, animal, object or scene represented as a solid shape of a single colour, usually black, with its edges matching the outline of the subject. The interior of a silhouette is featureless, and the silhou ...

of the realization under

parallel projection In three-dimensional geometry, a parallel projection (or axonometric projection) is a projection of an object in three-dimensional space onto a fixed plane, known as the '' projection plane'' or '' image plane'', where the '' rays'', known as ...

.

Tangent spheres

The realization of polyhedra using the

circle packing theorem The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles (in gen ...

provides another strengthening of Steinitz's theorem: 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 In mathematics, a unit sphere is simply a sphere of radius one around a given center. More generally, it is the set of points of distance 1 from a fixed central point, where different norms can be used as general notions of "distance". A u ...

, the

midsphere In geometry, the midsphere or intersphere of a polyhedron is a sphere which is tangent to every edge of the polyhedron. That is to say, it touches any given edge at exactly one point. Not every polyhedron has a midsphere, but for every convex ...

of the polyhedron. By performing a carefully chosen

Möbius transformation In geometry and complex analysis, a Möbius transformation of the complex plane is a rational function of the form f(z) = \frac of one complex variable ''z''; here the coefficients ''a'', ''b'', ''c'', ''d'' are complex numbers satisfying ''ad' ...

of a circle packing before transforming it into a polyhedron, it is possible to find a polyhedral realization that realizes all the symmetries of the underlying graph, in the sense that every

graph automorphism In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity. Formally, an automorphism of a graph is a permutation of the ...

is a symmetry of the polyhedral realization. More generally, if

G

is a polyhedral graph and

K

is any smooth three-dimensional

convex body In mathematics, a convex body in n-dimensional Euclidean space \R^n 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; that is to say, a point x lies in ...

, it is possible to find a polyhedral representation of

G

in which all edges are tangent to

K

. Circle packing methods can also be used to characterize the graphs of polyhedra that have a

circumsphere In geometry, a circumscribed sphere of a polyhedron is a sphere that contains the polyhedron and touches each of the polyhedron's vertices. The word circumsphere is sometimes used to mean the same thing, by analogy with the term ''circumcircle' ...

through all their vertices, or an

insphere In geometry, the inscribed sphere or insphere of a convex polyhedron is a sphere that is contained within the polyhedron and tangent to each of the polyhedron's faces. It is the largest sphere that is contained wholly within the polyhedron, and i ...

tangent to all of their faces. (The polyhedra with a circumsphere are also significant in

hyperbolic geometry In mathematics, hyperbolic geometry (also called Lobachevskian geometry or Bolyai–Lobachevskian geometry) is a non-Euclidean geometry. The parallel postulate of Euclidean geometry is replaced with: :For any given line ''R'' and point ''P' ...

as the ideal polyhedra.) In both cases, the existence of a sphere is equivalent to the solvability of a

system of linear inequalities In mathematics a linear inequality is an inequality (mathematics), inequality which involves a linear function. A linear inequality contains one of the symbols of inequality:. It shows the data which is not equal in graph form. * greater than * � ...

on positive real variables associated with each edge of the graph. In the case of the insphere, these variables must sum to exactly one on each face cycle of the graph, and to more than one on each non-face cycle. Dually, for the circumsphere, the variables must sum to one at each vertex, and more than one across each cut with two or more vertices on each side of the cut. Although there may be exponentially many linear inequalities to satisfy, a solution (if one exists) can be found in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

using the

ellipsoid method In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm which finds an ...

. The values of the variables from a solution determine the angles between pairs of circles in a circle packing whose corresponding polyhedron has the desired relation to its sphere.

Related results

In any dimension higher than three, the ''algorithmic Steinitz problem'' consists of determining whether a given lattice is the face lattice of a convex polytope. It is unlikely to have polynomial time complexity, as it is

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

and more strongly

complete Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies ...

for the

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 \exists X_1 \cdots \exists X_n \, F(X_1,\dots, X_n), where the variables X_i are interpre ...

, even for four-dimensional polytopes, by Richter-Gebert's universality theorem. Here, the existential theory of the reals is a class of computational problems that can be formulated in terms of finding real variables that satisfy a given system of polynomial equations and inequalities. For the algorithmic Steinitz problem, the variables of such a problem can be the vertex coordinates of a polytope, and the equations and inequalities can be used to specify the flatness of each face in the given face lattice and the convexity of each angle between faces. Completeness means that every other problem in this class can be transformed into an equivalent instance of the algorithmic Steinitz problem, in polynomial time. The existence of such a transformation implies that, if the algorithmic Steinitz problem has a polynomial time solution, then so does every problem in the existential theory of the reals, and every problem in NP. However, because a given graph may correspond to more than one face lattice, it is difficult to extend this completeness result to the problem of recognizing the graphs of 4-polytopes. Determining the computational complexity of this graph recognition problem remains open. Researchers have also found graph-theoretic characterizations of the graphs of certain special classes of three-dimensional non-convex polyhedra and four-dimensional convex polytopes. However, in both cases, the general problem remains unsolved. Indeed, even the problem of determining which

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices ...

s are the graphs of non-convex polyhedra (other than

K_4

for the tetrahedron and

K_7

for the Császár polyhedron) remains unsolved. Eberhard's theorem partially characterizes the

multiset In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that ...

s of

polygon In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed '' polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two t ...

s that can be combined to form the faces of a convex polyhedron. It can be proven by forming a 3-connected planar graph with the given set of polygon faces, and then applying Steinitz's theorem to find a polyhedral realization of that graph.

László Lovász László Lovász (; born March 9, 1948) is a Hungarian mathematician and professor emeritus at Eötvös Loránd University, best known for his work in combinatorics, for which he was awarded the 2021 Abel Prize jointly with Avi Wigderson. He wa ...

has shown a correspondence between polyhedral representations of graphs and matrices realizing the Colin de Verdière graph invariants of the same graphs. The Colin de Verdière invariant is the maximum

corank {{Unreferenced, date=December 2020 In mathematics, corank is complementary to the concept of the rank of a mathematical object, and may refer to the dimension of the left nullspace of a matrix, the dimension of the cokernel of a linear transforma ...

of a weighted

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple ...

of the graph, under some additional conditions that are irrelevant for polyhedral graphs. These are square

symmetric matrices In linear algebra, a symmetric matrix is a square matrix that is equal to its transpose. Formally, Because equal matrices have equal dimensions, only square matrices can be symmetric. The entries of a symmetric matrix are symmetric with r ...

indexed by the vertices, with the weight of vertex

i

in the diagonal coefficient

M_

and with the weight of edge

i,j

in the off-diagonal coefficients

M_

and

M_

. When vertices

i

and

j

are not adjacent, the coefficient

M_

is required to be zero. This invariant is at most three if and only if the graph is a

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. In other words, it can be drawn in such a way that no edges cro ...

. As Lovász shows, when the graph is polyhedral, a representation of it as a polyhedron can be obtained by finding a weighted adjacency matrix of corank three, finding three vectors forming a basis for its nullspace, using the coefficients of these vectors as coordinates for the vertices of a polyhedron, and scaling these vertices appropriately.

History

The history of Steinitz's theorem is described by , who notes its first appearance in a cryptic form in a publication of Ernst Steinitz, originally written in 1916. Steinitz provided more details in later lecture notes, published after his 1928 death. Although modern treatments of Steinitz's theorem state it as a graph-theoretic characterization of polyhedra, Steinitz did not use the language of graphs. The graph-theoretic formulation of the theorem was introduced in the early 1960s by

Branko Grünbaum Branko Grünbaum ( he, ברנקו גרונבאום; 2 October 1929 – 14 September 2018) was a Croatian-born mathematician of Jewish descentTheodore Motzkin Theodore Samuel Motzkin (26 March 1908 – 15 December 1970) was an Israeli- American mathematician. Biography Motzkin's father Leo Motzkin, a Ukrainian Jew, went to Berlin at the age of thirteen to study mathematics. He pursued university st ...

, with its proof also converted to graph theory in Grünbaum's 1967 text ''

Convex Polytopes ''Convex Polytopes'' is a graduate-level mathematics textbook about convex polytopes, higher-dimensional generalizations of three-dimensional convex polyhedra. It was written by Branko Grünbaum, with contributions from Victor Klee, Micha Perle ...

''. The work of Epifanov on Δ-Y and Y-Δ transforms, strengthening Steinitz's proof, was motivated by other problems than the characterization of polyhedra. credits Grünbaum with observing the relevance of this work for Steinitz's theorem. The Maxwell–Cremona correspondence between stress diagrams and polyhedral liftings was developed in a series of papers by

James Clerk Maxwell James Clerk Maxwell (13 June 1831 – 5 November 1879) was a Scottish mathematician and scientist responsible for the classical theory of electromagnetic radiation, which was the first theory to describe electricity, magnetism and ligh ...

from 1864 to 1870, based on earlier work of

Pierre Varignon Pierre Varignon (1654 – 23 December 1722) was a French mathematician. He was educated at the Jesuit College and the University of Caen, where he received his M.A. in 1682. He took Holy Orders the following year. Varignon gained his first ...

,

William Rankine William John Macquorn Rankine (; 5 July 1820 – 24 December 1872) was a Scottish mechanical engineer who also contributed to civil engineering, physics and mathematics. He was a founding contributor, with Rudolf Clausius and William Thomson ( ...

, and others, and was popularized in the late 19th century by Luigi Cremona. The observation that this correspondence can be used with the Tutte embedding to prove Steinitz's theorem comes from . The

circle packing theorem The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles (in gen ...

was proved by

Paul Koebe Paul Koebe (15 February 1882 – 6 August 1945) 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 ...

in 1936 and (independently) by E. M. Andreev in 1970; it was popularized in the mid-1980s by

William Thurston William Paul Thurston (October 30, 1946August 21, 2012) was an American mathematician. He was a pioneer in the field of low-dimensional topology and was awarded the Fields Medal in 1982 for his contributions to the study of 3-manifolds. Thursto ...

, who (despite citing Koebe and Andreev) is often credited as one of its discoverers. Andreev's version of the theorem was already formulated as a Steinitz-like characterization for certain polyhedra in

hyperbolic space In mathematics, hyperbolic space of dimension n is the unique simply connected, n-dimensional Riemannian manifold of constant sectional curvature equal to -1. It is homogeneous, and satisfies the stronger property of being a symmetric space. ...

, and the use of circle packing to realize polyhedra with midspheres comes from the work of Thurston. The problem of characterizing polyhedra with inscribed or circumscribed spheres, eventually solved using a method based on circle packing realizations, goes back to unpublished work of

René Descartes René Descartes ( or ; ; Latinized: Renatus Cartesius; 31 March 1596 – 11 February 1650) was a French philosopher, scientist, and mathematician, widely considered a seminal figure in the emergence of modern philosophy and science. Mathe ...

circa 1630 and to

Jakob Steiner Jakob Steiner (18 March 1796 – 1 April 1863) was a Swiss mathematician who worked primarily in geometry. Life Steiner was born in the village of Utzenstorf, Canton of Bern. At 18, he became a pupil of Heinrich Pestalozzi and afterwards s ...

in 1832; the first examples of polyhedra that have no realization with a circumsphere or insphere were given by Steinitz in 1928.

References

{{reflist, refs= {{citation , last1 = Aichholzer , first1 = Oswin , last2 = Cheng , first2 = Howard , last3 = Devadoss , first3 = Satyan L. , author3-link = Satyan Devadoss , last4 = Hackl , first4 = Thomas , last5 = Huber , first5 = Stefan , last6 = Li , first6 = Brian , last7 = Risteski , first7 = Andrej , contribution = What makes a Tree a Straight Skeleton? , contribution-url = http://2012.cccg.ca/papers/paper30.pdf , title = Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG'12) , year = 2012 {{citation , last = Andreev , first = E. M. , journal =

Matematicheskii Sbornik ''Matematicheskii Sbornik'' (russian: Математический сборник, abbreviated ''Mat. Sb.'') is a peer reviewed Russian mathematical journal founded by the Moscow Mathematical Society in 1866. It is the oldest successful Russian mat ...

, mr = 0259734 , pages = 445–478 , title = Convex polyhedra in Lobačevskiĭ spaces , url = http://mi.mathnet.ru/msb3382 , volume = 81 , year = 1970, issue = 123 {{citation , last = Balinski , first = M. L. , author-link = Michel Balinski , doi = 10.2140/pjm.1961.11.431 , doi-access = free , issue = 2 , journal =

Pacific Journal of Mathematics The Pacific Journal of Mathematics is a mathematics research journal supported by several universities and research institutes, and currently published on their behalf by Mathematical Sciences Publishers, a non-profit academic publishing organisati ...

, mr = 0126765 , pages = 431–434 , title = On the graph structure of convex polyhedra in {{mvar, n-space , url = https://projecteuclid.org/euclid.pjm/1103037323 , volume = 11 , year = 1961 {{citation , last = Barnette , first = David W. , doi = 10.1007/BF02771563 , issue = 3 , journal =

Israel Journal of Mathematics '' Israel Journal of Mathematics'' is a peer-reviewed mathematics journal published by the Hebrew University of Jerusalem (Magnes Press). Founded in 1963, as a continuation of the ''Bulletin of the Research Council of Israel'' (Section F), the j ...

, mr = 262923 , pages = 304–308 , s2cid = 120791830 , title = Projections of 3-polytopes , volume = 8 , year = 1970 {{citation , last1 = Bern , first1 = Marshall W. , last2 = Eppstein , first2 = David , author2-link = David Eppstein , editor1-last = Dehne , editor1-first = Frank K. H. A. , editor2-last = Sack , editor2-first = Jörg-Rüdiger , editor3-last = Tamassia , editor3-first = Roberto , arxiv = cs/0101006 , s2cid = 3266233 , contribution = Optimal Möbius transformations for information visualization and meshing , doi = 10.1007/3-540-44634-6_3 , pages = 14–25 , publisher = Springer , series =

Lecture Notes in Computer Science ''Lecture Notes in Computer Science'' is a series of computer science books published by Springer Science+Business Media since 1973. Overview The series contains proceedings, post- proceedings, monographs, and Festschrift In academia, a ''F ...

, title = Algorithms and Data Structures, 7th International Workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001, Proceedings , volume = 2125 , year = 2001 {{citation , last1 = Barnette , first1 = David W. , last2 = Grünbaum , first2 = Branko , author2-link = Branko Grünbaum , editor1-first = G. , editor1-last = Chartrand , editor1-link = Gary Chartrand , editor2-first = S. F. , editor2-last = Kapoor , contribution = On Steinitz's theorem concerning convex 3-polytopes and on some properties of planar graphs , doi = 10.1007/BFb0060102 , mr = 0250916 , pages = 27–40 , publisher = Springer , series =

Lecture Notes in Mathematics ''Lecture Notes in Mathematics'' is a book series in the field of mathematics, including articles related to both research and teaching. It was established in 1964 and was edited by A. Dold, Heidelberg and B. Eckmann, Zürich. Its publisher is Sp ...

, title = The Many Facets of Graph Theory: Proceedings of the Conference held at Western Michigan University, Kalamazoo, MI., October 31 – November 2, 1968 , volume = 110 , year = 1969 {{citation , last1 = Barnette , first1 = David W. , last2 = Grünbaum , first2 = Branko , author2-link = Branko Grünbaum , doi=10.2140/pjm.1970.32.299 , doi-access = free , issue = 2 , journal =

Pacific Journal of Mathematics The Pacific Journal of Mathematics is a mathematics research journal supported by several universities and research institutes, and currently published on their behalf by Mathematical Sciences Publishers, a non-profit academic publishing organisati ...

, mr = 0259744 , pages = 299–306 , title = Preassigning the shape of a face , url = http://projecteuclid.org/euclid.pjm/1102977361 , volume = 32 , year = 1970 {{citation , last1 = Blind , first1 = Roswitha , author1-link = Roswitha Blind , last2 = Mani-Levitska , first2 = Peter , doi = 10.1007/BF01830678 , issue = 2–3 , journal =

Aequationes Mathematicae ''Aequationes Mathematicae'' is a mathematical journal. It is primarily devoted to functional equations, but also publishes papers in dynamical systems, combinatorics, and geometry. As well as publishing regular journal submissions on these topic ...

, mr = 921106 , pages = 287–297 , s2cid = 120222616 , title = Puzzles and polytope isomorphisms , volume = 34 , year = 1987 {{citation , last = Brandes , first = Ulrik , author1-link = Ulrik Brandes , editor1-last = Kaufmann , editor1-first = Michael , editor2-last = Wagner , editor2-first = Dorothea , editor2-link = Dorothea Wagner , contribution = Drawing on physical analogies , doi = 10.1007/3-540-44969-8_4 , location = Berlin , mr = 1880146 , pages = 71–86 , publisher = Springer , series =

Lecture Notes in Computer Science ''Lecture Notes in Computer Science'' is a series of computer science books published by Springer Science+Business Media since 1973. Overview The series contains proceedings, post- proceedings, monographs, and Festschrift In academia, a ''F ...

, title = Drawing Graphs: Methods and Models , volume = 2025 , year = 2001, citeseerx = 10.1.1.9.5023 {{citation , last1 = Buchin , first1 = Kevin , last2 = Schulz , first2 = André , editor1-last = de Berg , editor1-first = Mark , editor1-link = Mark de Berg , editor2-last = Meyer , editor2-first = Ulrich , contribution = On the number of spanning trees a planar graph can have , doi = 10.1007/978-3-642-15775-2_10 , isbn = 978-3-642-15774-5 , mr = 2762847 , pages = 110–121 , publisher = Springer , series =

Lecture Notes in Computer Science ''Lecture Notes in Computer Science'' is a series of computer science books published by Springer Science+Business Media since 1973. Overview The series contains proceedings, post- proceedings, monographs, and Festschrift In academia, a ''F ...

, title = Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010, Proceedings, Part I , volume = 6346 , year = 2010, citeseerx = 10.1.1.746.942 , s2cid = 42211547 {{citation , last1 = Brightwell , first1 = Graham R. , author1-link = Graham Brightwell , last2 = Scheinerman , first2 = Edward R. , author2-link = Ed Scheinerman , doi = 10.1137/0406017 , issue = 2 , journal =

SIAM Journal on Discrete Mathematics '' SIAM Journal on Discrete Mathematics'' is a peer-reviewed mathematics journal published quarterly by the Society for Industrial and Applied Mathematics (SIAM). The journal includes articles on pure and applied discrete mathematics. It was esta ...

, mr = 1215229 , pages = 214–229 , title = Representations of planar graphs , volume = 6 , year = 1993 {{citation , last1 = Chang , first1 = Hsien-Chih , last2 = Cossarini , first2 = Marcos , last3 = Erickson , first3 = Jeff , editor1-last = Barequet , editor1-first = Gill , editor2-last = Wang , editor2-first = Yusu , arxiv = 1707.04683 , contribution = Lower bounds for electrical reduction on surfaces , doi = 10.4230/LIPIcs.SoCG.2019.25 , isbn = 978-3-95977-104-7 , location = Dagstuhl, Germany , mr = 3968611 , pages = 25:1–25:16 , publisher = Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik , series = Leibniz International Proceedings in Informatics (LIPIcs) , title = 35th International Symposium on Computational Geometry (SoCG 2019) , volume = 129 , year = 2019 {{citation , last1 = Chrobak , first1 = Marek , last2 = Goodrich , first2 = Michael T. , author2-link = Michael T. Goodrich , last3 = Tamassia , first3 = Roberto , author3-link = Roberto Tamassia , contribution = Convex drawings of graphs in two and three dimensions , doi = 10.1145/237218.237401 , pages = 319–328 , publisher = ACM , s2cid = 1015103 , title = Proceedings of the 12th ACM Symposium on Computational Geometry (SoCG '96) , title-link = Symposium on Computational Geometry , year = 1996 {{citation , last1 = Demaine , first1 = Erik D. , author1-link = Erik Demaine , last2 = Schulz , first2 = André , arxiv = 1403.7980 , doi = 10.1007/s00454-017-9887-6 , issue = 4 , journal =

Discrete & Computational Geometry '' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational ge ...

, mr = 3639604 , pages = 782–809 , title = Embedding stacked polytopes on a polynomial-size grid , volume = 57 , year = 2017, s2cid = 104867 {{citation , last1 = Dillencourt , first1 = Michael B. , last2 = Smith , first2 = Warren D. , doi = 10.1016/0012-365X(95)00276-3 , issue = 1–3 , journal =

Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continu ...

, mr = 1420521 , pages = 63–77 , title = Graph-theoretical conditions for inscribability and Delaunay realizability , url = https://escholarship.org/uc/item/0hf4118d , volume = 161 , year = 1996 {{citation , last1 = Eades , first1 = Peter , author1-link = Peter Eades , last2 = Garvan , first2 = Patrick , editor-last = Brandenburg , editor-first = Franz-Josef , contribution = Drawing stressed planar graphs in three dimensions , doi = 10.1007/BFb0021805 , mr = 1400675 , pages = 212–223 , publisher = Springer , series =

Lecture Notes in Computer Science ''Lecture Notes in Computer Science'' is a series of computer science books published by Springer Science+Business Media since 1973. Overview The series contains proceedings, post- proceedings, monographs, and Festschrift In academia, a ''F ...

, title = Graph Drawing, Symposium on Graph Drawing, GD '95, Passau, Germany, September 20-22, 1995, Proceedings , volume = 1027 , year = 1995, doi-access = free {{citation , last1 = Erickson , first1 = Jeff , last2 = Lin , first2 = Patrick , editor1-last = Cabello , editor1-first = Sergio , editor2-last = Chen , editor2-first = Danny Z. , arxiv = 2003.10057 , contribution = A toroidal Maxwell–Cremona-Delaunay correspondence , doi = 10.4230/LIPIcs.SoCG.2020.40 , isbn = 978-3-95977-143-6 , location = Dagstuhl, Germany , pages = 40:1–40:17 , publisher = Schloss Dagstuhl–Leibniz-Zentrum für Informatik , series = Leibniz International Proceedings in Informatics (LIPIcs) , title = 36th International Symposium on Computational Geometry (SoCG 2020) , volume = 164 , year = 2020, s2cid = 209514295 {{citation , last1 = Eppstein , first1 = David , author1-link = David Eppstein , last2 = Mumford , first2 = Elena , doi = 10.20382/jocg.v5i1a10 , issue = 1 , journal = Journal of Computational Geometry , mr = 3259910 , pages = 179–244 , title = Steinitz theorems for simple orthogonal polyhedra , volume = 5 , year = 2014, s2cid = 8531578 {{citation , last = Epifanov , first = G. V. , journal =

Doklady Akademii Nauk SSSR The ''Proceedings of the USSR Academy of Sciences'' (russian: Доклады Академии Наук СССР, ''Doklady Akademii Nauk SSSR'' (''DAN SSSR''), french: Comptes Rendus de l'Académie des Sciences de l'URSS) was a Soviet journal that ...

, language = ru , mr = 0201337 , pages = 19–22 , title = Reduction of a plane graph to an edge by star-triangle transformations , url = http://mi.mathnet.ru/dan31994 , volume = 166 , year = 1966 , zbl = 0149.21301 {{citation , last = Federico , first = Pasquale Joseph , author-link = Pasquale Joseph Federico , page = 52 , publisher = Springer , series = Sources in the History of Mathematics and Physical Sciences , title = Descartes on Polyhedra: A Study of the "De solidorum elementis" , title-link = Descartes on Polyhedra , volume = 4 , year = 1982 {{citation , last = Grünbaum , first = Branko , author-link = Branko Grünbaum , contribution = 13.1 Steinitz's theorem , edition = 2nd , isbn = 0-387-40409-0 , pages = 235–244 , publisher = Springer-Verlag , series =

Graduate Texts in Mathematics Graduate Texts in Mathematics (GTM) ( ISSN 0072-5285) is a series of graduate-level textbooks in mathematics published by Springer-Verlag. The books in this series, like the other Springer-Verlag mathematics series, are yellow books of a standa ...

, title = Convex Polytopes , title-link = Convex Polytopes , volume = 221 , year = 2003 {{citation , last = Grünbaum , first = Branko , author-link = Branko Grünbaum , doi = 10.1016/j.disc.2005.09.037 , hdl = 1773/2276 , hdl-access = free , issue = 3–5 , journal =

Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continu ...

, mr = 2287486 , pages = 445–463 , title = Graphs of polyhedra; polyhedra as graphs , volume = 307 , year = 2007 {{citation , last = Hart , first = George W. , authorlink = George W. Hart , issue = 3 , journal = Mathematica in Education and Research , pages = 5–10 , title = Calculating canonical polyhedra , url = http://library.wolfram.com/infocenter/Articles/2012/ , volume = 6 , year = 1997 {{citation , last1 = Hong , first1 = Seok-Hee , author1-link = Seok-Hee Hong , last2 = Nagamochi , first2 = Hiroshi , doi = 10.1007/s00453-011-9570-x , issue = 4 , journal =

Algorithmica ''Algorithmica'' is a monthly peer-reviewed scientific journal focusing on research and the application of computer science algorithms. The journal was established in 1986 and is published by Springer Science+Business Media. The editor in chief is ...

, mr = 2852056 , pages = 1022–1076 , s2cid = 12622357 , title = Extending Steinitz's theorem to upward star-shaped polyhedra and spherical polyhedra , volume = 61 , year = 2011 {{citation , last = Kalai , first = Gil , authorlink = Gil Kalai , doi = 10.1016/0097-3165(88)90064-7 , doi-access = free , issue = 2 , journal =

Journal of Combinatorial Theory The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicat ...

, series = Series A , mr = 964396 , pages = 381–383 , title = A simple way to tell a simple polytope from its graph , volume = 49 , year = 1988 {{citation , last = Koebe , first = Paul , author-link = Paul Koebe , journal = Berichte über die Verhandlungen der Sächsischen Akademie der Wissenschaften zu Leipzig: Mathematisch-Physische Klasse , language = de , pages = 141–164 , title = Kontaktprobleme der Konformen Abbildung , volume = 88 , year = 1936 {{citation , last = Lovász , first = László , authorlink = László Lovász , doi = 10.1006/jctb.2000.2027 , doi-access = free , issue = 2 , journal =

Journal of Combinatorial Theory The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicat ...

, mr = 1842113 , pages = 223–236 , series = Series B , title = Steinitz representations of polyhedra and the Colin de Verdière number , volume = 82 , year = 2001 {{citation , last = Malkevitch , first = Joseph , publisher = City University of New York , title = Techniques for proving combinatorial theorems about 3-polytopes , url = https://www.york.cuny.edu/~malk/geometricstructures/steinitz.html , work = Geometric Structures (course notes) {{mathworld , urlname = PolyhedralGraph , title = Polyhedral graph, mode=cs2 {{citation , last = Maxwell , first = J. Clerk , authorlink = James Clerk Maxwell , doi = 10.1080/14786446408643663 , journal =

Philosophical Magazine The ''Philosophical Magazine'' is one of the oldest scientific journals published in English. It was established by Alexander Tilloch in 1798;John Burnett"Tilloch, Alexander (1759–1825)" Oxford Dictionary of National Biography, Oxford Unive ...

, series=4th Series , pages = 250–261 , title = On reciprocal figures and diagrams of forces , volume = 27 , year = 1864, issue = 182 {{citation , last1 = Onn , first1 = Shmuel , last2 = Sturmfels , first2 = Bernd , author2-link = Bernd Sturmfels , issue = 1 , journal = Beiträge zur Algebra und Geometrie , mr = 1287206 , pages = 125–129 , title = A quantitative Steinitz' theorem , url = https://emis.de/journals/BAG/vol.35/no.1/b35h1onb.ps.gz , volume = 35 , year = 1994 {{citation , last = Richter-Gebert , first = Jürgen , doi = 10.1007/BFb0093761 , isbn = 978-3-540-62084-6 , mr = 1482230 , publisher = Springer-Verlag , series =

Lecture Notes in Mathematics ''Lecture Notes in Mathematics'' is a book series in the field of mathematics, including articles related to both research and teaching. It was established in 1964 and was edited by A. Dold, Heidelberg and B. Eckmann, Zürich. Its publisher is Sp ...

, title = Realization Spaces of Polytopes , volume = 1643 , year = 1996, citeseerx = 10.1.1.2.3495 {{citation , last = Rivin , first = Igor , authorlink = Igor Rivin , doi = 10.2307/2118652 , issue = 1 , journal =

Annals of Mathematics The ''Annals of Mathematics'' is a mathematical journal published every two months by Princeton University and the Institute for Advanced Study. History The journal was established as ''The Analyst'' in 1874 and with Joel E. Hendricks as t ...

, series = Second Series , jstor = 2118652 , mr = 1370757 , pages = 51–70 , title = A characterization of ideal polyhedra in hyperbolic 3-space , volume = 143 , year = 1996 {{citation , last1 = Ribó Mor , first1 = Ares , last2 = Rote , first2 = Günter , last3 = Schulz , first3 = André , arxiv = 0908.0488 , doi = 10.1007/s00454-010-9301-0 , issue = 1 , journal =

Discrete & Computational Geometry '' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational ge ...

, mr = 2765520 , pages = 65–87 , s2cid = 10141034 , title = Small grid embeddings of 3-polytopes , volume = 45 , year = 2011 {{citation , last = Schramm , first = Oded , author-link = Oded Schramm , doi = 10.1007/BF02773845 , issue = 3 , journal =

Israel Journal of Mathematics '' Israel Journal of Mathematics'' is a peer-reviewed mathematics journal published by the Hebrew University of Jerusalem (Magnes Press). Founded in 1963, as a continuation of the ''Bulletin of the Research Council of Israel'' (Section F), the j ...

, mr = 1135221 , pages = 321–341 , title = Existence and uniqueness of packings with specified combinatorics , volume = 73 , year = 1991, s2cid = 121855202 ; see discussion following Corollary 3.8, p. 329 {{citation , last = Schramm , first = Oded , author-link = Oded Schramm , bibcode = 1992InMat.107..543S , doi = 10.1007/BF01231901 , issue = 3 , journal =

Inventiones Mathematicae ''Inventiones Mathematicae'' is a mathematical journal published monthly by Springer Science+Business Media. It was established in 1966 and is regarded as one of the most prestigious mathematics journals in the world. The current managing editors ...

, mr = 1150601 , pages = 543–560 , s2cid = 189830473 , title = How to cage an egg , volume = 107 , year = 1992 {{citation , last = Schaefer , first = Marcus , editor-last = Pach , editor-first = János , editor-link = János Pach , contribution = Realizability of graphs and linkages , doi = 10.1007/978-1-4614-0110-0_24 , mr = 3205168 , pages = 461–482 , publisher = Springer , location = New York , title = Thirty Essays on Geometric Graph Theory , year = 2013, citeseerx = 10.1.1.220.9651 {{citation , last = Schulz , first = André , doi = 10.7155/jgaa.00216 , doi-access = free , issue = 1 , journal =

Journal of Graph Algorithms and Applications The ''Journal of Graph Algorithms and Applications'' is an open access peer-reviewed scientific journal covering the subject of graph algorithms and graph drawing. The journal was established in 1997 and the editor-in-chief is Giuseppe Liotta (Univ ...

, mr = 2776000 , pages = 33–52 , title = Drawing 3-polytopes with good vertex resolution , volume = 15 , year = 2011 {{citation , last = Steiner , first = Jakob , author-link = Jakob Steiner , language = de , contribution = Question 77 , contribution-url = https://archive.org/details/systematischeen02steigoog/page/n343 , page = 316 , publisher = G. Fincke , location = Berlin , title = Systematische Entwicklung der Abhängigkeit geometrischer Gestalten von einander , url = https://archive.org/details/systematischeen02steigoog , year = 1832 {{citation , last = Steinitz , first = Ernst , author-link = Ernst Steinitz , contribution = IIIAB12: Polyeder und Raumeinteilungen , contribution-url = https://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN360609767&DMDID=dmdlog203 , language = de , quote = Abgeschlossen am 31. August 1916 , pages = 1–139 , title = Encyclopädie der mathematischen Wissenschaften , volume = Band 3 (Geometries) , year = 1922 {{citation , last = Steinitz , first = Ernst , doi = 10.1515/crll.1928.159.133 , journal =

Journal für die Reine und Angewandte Mathematik ''Crelle's Journal'', or just ''Crelle'', is the common name for a mathematics journal, the ''Journal für die reine und angewandte Mathematik'' (in English language, English: ''Journal for Pure and Applied Mathematics''). History The journal wa ...

, language = de , mr = 1581158 , pages = 133–143 , title = Über isoperimetrische Probleme bei konvexen Polyedern , volume = 1928 , year = 1928, issue = 159 , s2cid = 199546274 {{citation , last = Stephenson , first = Kenneth , issue = 11 , journal =

Notices of the American Mathematical Society ''Notices of the American Mathematical Society'' is the membership journal of the American Mathematical Society (AMS), published monthly except for the combined June/July issue. The first volume appeared in 1953. Each issue of the magazine since ...

, mr = 2011604 , pages = 1376–1388 , title = Circle packing: a mathematical tale , url = https://www.ams.org/notices/200311/fea-stephenson.pdf , volume = 50 , year = 2003, citeseerx = 10.1.1.101.5592 {{citation , last = Sturmfels , first = Bernd , author-link = Bernd Sturmfels , doi = 10.1112/jlms/s2-35.2.314 , issue = 2 , journal =

Journal of the London Mathematical Society The London Mathematical Society (LMS) is one of the United Kingdom's learned societies for mathematics (the others being the Royal Statistical Society (RSS), the Institute of Mathematics and its Applications (IMA), the Edinburgh Mathematica ...

, mr = 881520 , pages = 314–326 , series = Second Series , title = Boundary complexes of convex polytopes cannot be characterized locally , volume = 35 , year = 1987, citeseerx = 10.1.1.106.3222 {{citation , last = Eppstein , first = David , author-link = David Eppstein , arxiv = 1510.03152 , doi = 10.1007/s00454-020-00177-0 , issue = 2 , journal =

Discrete & Computational Geometry '' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational ge ...

, mr = 4131546 , pages = 259–289 , title = Treetopes and their graphs , volume = 64 , year = 2020, s2cid = 213885326 {{citation , last = Truemper , first = K. , doi = 10.1002/jgt.3190130202 , issue = 2 , journal =

Journal of Graph Theory The ''Journal of Graph Theory'' is a peer-reviewed mathematics journal specializing in graph theory and related areas, such as structural results about graphs, graph algorithms with theoretical emphasis, and discrete optimization on graphs. Th ...

, mr = 994737 , pages = 141–148 , title = On the delta-wye reduction for planar graphs , volume = 13 , year = 1989 {{Citation , last = Tutte , first = W. T. , authorlink = W. T. Tutte , doi = 10.1112/plms/s3-13.1.743 , journal =

Proceedings of the London Mathematical Society The London Mathematical Society (LMS) is one of the United Kingdom's learned societies for mathematics (the others being the Royal Statistical Society (RSS), the Institute of Mathematics and its Applications (IMA), the Edinburgh Mathematical ...

, mr = 0158387 , pages = 743–767 , title = How to draw a graph , volume = 13 , year = 1963 {{citation , last = Whiteley , first = Walter , author-link = Walter Whiteley , hdl = 2099/989 , journal = Structural Topology , mr = 721947 , pages = 13–38 , title = Motions and stresses of projected polyhedra , volume = 7 , year = 1982 {{citation , last = Ziegler , first = Günter M. , author-link = Günter M. Ziegler , editor1-last = Miller , editor1-first = Ezra , editor2-last = Reiner , editor2-first = Victor , editor3-last = Sturmfels , editor3-first = Bernd , editor3-link = Bernd Sturmfels , contribution = Convex polytopes: extremal constructions and ''f''-vector shapes. Section 1.3: Steinitz's theorem via circle packings , isbn = 978-0-8218-3736-8 , pages = 628–642 , publisher =

American Mathematical Society The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings ...

, series = IAS/Park City Mathematics Series , title = Geometric Combinatorics , volume = 13 , year = 2007 {{citation , last = Ziegler , first = Günter M. , authorlink = Günter M. Ziegler , arxiv = math/0412093 , contribution = Polyhedral surfaces of high genus , doi = 10.1007/978-3-7643-8621-4_10 , isbn = 978-3-7643-8620-7 , mr = 2405667 , pages = 191–213 , publisher = Springer , s2cid = 15911143 , series = Oberwolfach Seminars , title = Discrete Differential Geometry , volume = 38 , year = 2008 {{citation , last = Ziegler , first = Günter M. , author-link = Günter M. Ziegler , contribution = Chapter 4: Steinitz' Theorem for 3-Polytopes , isbn = 0-387-94365-X , pages = 103–126 , publisher = Springer-Verlag , series =

Graduate Texts in Mathematics Graduate Texts in Mathematics (GTM) ( ISSN 0072-5285) is a series of graduate-level textbooks in mathematics published by Springer-Verlag. The books in this series, like the other Springer-Verlag mathematics series, are yellow books of a standa ...

, title = Lectures on Polytopes , volume = 152 , year = 1995 Planar graphs Geometric graph theory Polyhedral combinatorics Theorems in graph theory Theorems in discrete geometry