Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 35 (1994), No. 1, 125-129.

A Quantitative Steinitz’ Theorem

Shmuel Onn^{1} and Bernd Sturmfels^{2}

Department of Operations Research, Technion Haifa, 32000, Israel Department of Mathematics, Cornell University Ithaca, NY 14853, U.S.A.

Abstract. Any 3-dimensional convex polytope with n vertices can be realized in Euclidean 3-space with all coordinates of all vertices being integers of absolute value not exceeding n^{169n^{3}}.

1. Introduction

The following classical theorem of Ernst Steinitz [6] gives a characterization of combinatorial types of 3-dimensional convex polytopes (or, 3-polytopes, for short) in terms of their edge graphs.

Theorem 1.1 (Steinitz’ Theorem). A graph is isomorphic to the edge graph of a 3-polytope if and only if it is 3-connected and planar.

The hard part of this theorem is the “if” direction; the usual proofs proceed by constructing the 3-polytope from its given graph. It is known (see [2] or [9]) that these constructions can be carried out over the field of rational numbers. This implies that all 3-polytopes admit an embedding with all coordinates of all vertices being integers. The following question then arises. Let f(n) be the smallest integer such that any 3-polytope with n vertices can be embedded with integer coordinates of absolute value not exceeding f(n). How fast does f(n) grow with n? From Steinitz’ proof one derives an upper bound on f(n) which is doubly exponential in n. The purpose of this note is to provide the following singly exponential upper bound on f(n).

Theorem 1.2. Any 3-polytope with n vertices can be realized in Euclidean 3-space with all coordinates of all vertices being integers of absolute value not exceeding n^{169n^{3}}.

1 Supported in part by the Alexander von Humboldt Stiftung.

2 Supported in part by the National Science Foundation and the David and Lucile Packard Foundation.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}1994 Heldermann Verlag, Berlin

This is somewhat surprising: if a realization is required for all order types of point configurations rather than for convex polytopes, then a doubly exponential lower bound is available even in the plane [1]. We remark that no characterization of the combinatorial structure of polytopes in dimensions higher than 3 is known. Also, starting in dimension 8, there are polytopes which admit no rational embedding (see [9]), in which case the quantitative analysis would be restricted to the class of rational polytopes. An important question left open here is whether the rate of growth of f(n) is indeed singly exponential (in which case a matching lower bound is desirable), or whether f(n) can in fact be bounded from above by a polynomial in n.

2. Preparation

Let G = (V, E) be a planar, 3-connected graph. Thus, V is the set of vertices of G and E is its set of edges; we shall use the short notation uv for an edge {u, v} ∈ E, where u, v ∈ V. A theorem of Whitney [8] asserts that the embedding of G into the plane (or the 2-sphere) is topologically unique. Thus, the set of faces of G is well defined: a face is a subset of V which induces a cycle bounding a face in the unique planar embedding of G. In particular, the combinatorial type of a 3-polytope P is determined by its edge graph G. We shall also make use of the planar dual G^{∗} of G, which is again 3-connected and planar. The vertex set of G^{∗} is the set of faces of G and uv is an edge of G^{∗} whenever u and v are adjacent faces in the planar embedding of G. Planar duality is an involution, so that (G^{∗})^{∗} = G.

For the proof of our result we need the following lemma from linear algebra. It can be deduced easily from Cramer’s rule, Caratheodory’s theorem [2] and Hadamard’s bound [5]. Lemma 2.1. Consider a system of linear equations and inequalities in n indeterminates

∑_{k=1}^{n} a_{i,k}x_{k} = b_{i}  (i ∈ I),  ∑_{k=1}^{n} a_{j,k}x_{k} ≥ b_{j}  (j ∈ J),

where all a_{r,s} and b_{r} are integers of absolute value ≤ M. If this system is solvable, then it has a solution x_{1} = \frac{p_{1}}{D} , ⋯, x_{n} = \frac{p_{n}}{D} with D, p_{1}, ⋯, p_{n} integers of absolute value at most ≤ n^{n/2}M^{n}.

We shall base our argument on the following well-known connection between Steinitz’ theorem and rigidity theory.

Theorem 2.2 (Maxwell’s Theorem). Let G = (V, E) be a 3-connected planar graph containing a triangular face F = {v_{1}, v_{2}, v_{3}}, and let f : F ⟶ IR^{2} be an embedding of F as a triangle in the plane. Let λ be a positive stress on G, i.e., an assignment of a positive real number λ(e) to each edge e. Then the following hold:

1. The map f can be uniquely extended to an embedding f : V ⟶ IR^{2} of the graph G, which is an equilibrium with respect to the stress λ, i.e., an embedding satisfying

∑_{{u: uv∈E}} λ(uv)(f(u) − f(v)) = 0 for all v ∈ V \ F.

2. Any equilibrium f with respect to a positive stress on G can be factored as f = π ∘ g, where g : V ⟶ IR^{3} is an embedding such that the 3-polytope conv (g(V)) has the edge graph G, and π denotes the orthogonal projection π : IR^{3} → IR^{2} : (x, y, z) ↦ (x, y).

The origins of Theorem 2.2 can be traced back to Maxwell [4]. The first complete proof was published by Whiteley in [7]. Another self-contained proof and computational information on stresses and equilibria can be found in [3]; the first part, as stated above, follows from assertion 2.1.3 in this reference, and the second part from assertions 2.1.4, 2.3.1, 3.3.5 and 3.6.1 in [3].

3. A singly exponential upper bound

Lemma 3.1 For any 3-connected, planar graph G = (V, E) containing a triangular face F = {v_{1}, v_{2}, v_{3}}, there exists an embedding g : V → IR^{3} such that G is the edge graph of conv (g(V)) and the coordinates of each vertex g(v) are integers of absolute value ≤ n^{7n^{2}}, where n is the number of vertices of V.

Proof. Given G = (V, E) as above, we embed the triangle F = {v_{1}, v_{2}, v_{3}} by putting

f′(v_{1}) = (x_{1}, y_{1}) = (0, 0), f′(v_{2}) = (x_{2}, y_{2}) = (1, 0), f′(v_{3}) = (x_{3}, y_{3}) = (0, 1),

and we consider the stress given by λ(e) = 1 for all edges e. Write V = {v_{1}, ⋯, v_{n}} and f′(v_{i}) = (x_{i}, y_{i}) with x_{i}, y_{i} indeterminates for i ≥ 4. The first assertion of Theorem 2.2 guarantees the existence of an equilibrium f′ with respect to λ, i.e., a solution to the following system of linear equations in these 2(n − 3) indeterminates:

∑_{{v_{j}: v_{j}v_{i}∈E}}(x_{j} − x_{i}) = 0, ∑_{{v_{j}: v_{j}v_{i}∈E}}(y_{j} − y_{i}) = 0  (i = 4, ⋯, n).

Each coefficient in this linear system is an integer of absolute value at most n. Lemma 2.1 implies that there is a solution x_{4} = \frac{p_{4}}{D} , ⋯, x_{n} = \frac{p_{n}}{D} , y_{4} = \frac{q_{4}}{D} , ⋯, y_{n} = \frac{q_{n}}{D} with D, p_{4}, ⋯, p_{n}, q_{4}, ⋯, q_{n} integers of absolute value less than 2^{n}n^{3n}. But then f = D · f′ is an equilibrium with respect to the same stress λ, which has all coordinates integral and of absolute value ≤ 2^{n}n^{3n}.

We now proceed to find a map g : V ⟶ IR^{3}, the existence of which is guaranteed by the second assertion of Theorem 2.2, such that f = π ∘ g and conv(g(V)) has the edge graph G. Write g(v_{i}) = (x_{i}, y_{i}, z_{i}), where (x_{i}, y_{i}) = f(v_{i}) and z_{i} is an indeterminate.

Given any four vertices v_{i}, v_{j}, v_{k}, v_{l} ∈ V, we shall use the bracket notation

[v_{i}, v_{j}, v_{k}, v_{l}] := det [ \begin{matrix}x_{i} & x_{j} & x_{k} & x_{l} \\ y_{i} & y_{j} & y_{k} & y_{l} \\ z_{i} & z_{j} & z_{k} & z_{l} \\ 1 & 1 & 1 & 1 \end{matrix} ]

for the corresponding determinant. Note that [v_{i}, v_{j}, v_{k}, v_{l}] is a linear form in z_{i}, z_{j}, z_{k}, z_{l}.

Let F_{1}, ⋯, F_{m} be all the faces of G. Fix three distinct vertices u_{i}, v_{i}, w_{i} in each face F_{i}. Suppose that g : V ⟶ IR^{3} is an embedding such that f = π∘g and P = conv(g(V)) has the edge graph G. Consider a face F_{i}. For any vertex v, the sign sign[u_{i}, v_{i}, w_{i}, v] ∈ {−1, 0, +1} is 0 if g(v) lies on the affine plane H_{i} in IR^{3} spanned by g(u_{i}), g(v_{i}), g(w_{i}), is −1 if v lies strictly on one side of H_{i}, and is +1 if v lies strictly on the other side of H_{i}. But H_{i} is the affine plane supporting P at its face F_{i}, so all vertices not in F_{i} lie on the same side of H_{i}. Therefore sign[u_{i}, v_{i}, w_{i}, v] = 0 if v ∈ F_{i}, and sign[u_{i}, v_{i}, w_{i}, v] = ϵ_{i} if v ∉ F_{i}, where ϵ_{i} is either −1 or +1. Moreover, multiplying z_{1}, ⋯, z_{n} by a large positive number if necessary, we may assume that the following inequality holds for all i and all v ∉ F_{i}:

ϵ_{i} · [u_{i}, v_{i}, w_{i}, v] ≥ 1.

We conclude that the desired embedding corresponds to any solution of the following system of linear equations and inequalities in the indeterminates z_{1}, ⋯, z_{n}:

[u_{i}, v_{i}, w_{i}, v] = 0 (v ∈ F_{i}),  ϵ_{i} · [u_{i}, v_{i}, w_{i}, v] ≥ 1 (v ∉ F_{i})  (i = 1, ⋯, m).

By the construction of f, the x, y coordinates of all vertices are integers of absolute value not exceeding 2^{n}n^{3n}, and so each coefficient in this system, which is a 3 × 3 minor of some bracket [u_{i}, v_{i}, w_{i}, v], has absolute value not exceeding

3 ! (2^{n}n^{3n})^{2} = 6 · 4^{n}n^{6n}.

Letting z_{1}, ⋯, z_{n} be a solution to this system of bounded size as guaranteed by Lemma 2.1, and multiplying z_{1}, ⋯, z_{n} by their common denominator if necessary, we obtain a solution yielding an embedding g of V with all coordinates integers of absolute value less than n^{7n^{2}}.

Proof of Theorem 1.2. For any planar, 3-connected graph G = (V, E) we must construct an embedding g : V → IR^{3} such that G is the edge graph of P = conv(g(V)) and the vertices of P have integral coordinates of the asserted size. Let n be the number of vertices and m the number of faces of G. It is known (see [2], p. 236) that G contains either a triangular face or a trivalent vertex. In the former case, Theorem 1.2 follows from Lemma 3.1. Otherwise G has a trivalent vertex, so its planar dual G^{∗} has a triangular face; by Lemma 3.1, the polar polytope P^{∗} with graph G^{∗} has an embedding g^{∗} with integer coordinates of absolute value at most

m^{7m^{2}} < (2n)^{28n^{2}}.

Here we have used the easy inequality m ≤ 2n − 4.

Translating P^{∗} if necessary (and at most doubling the size of its coordinates), we may assume that P^{∗} has the origin in its interior. We recover a polytope P with edge graph G as

P = {v ∈ IR^{3} : ⟨g^{∗}(u_{i}), v⟩ ≤ 1 i = 1, ⋯, m},

where u_{1}, ⋯, u_{m} are the vertices of G^{∗}. Each vertex v_{i} of the polytope P is obtained as the unique solution to a system of linear equations

⟨g^{∗}(u_{i_{1}}), v_{i}⟩ = ⟨g^{∗}(u_{i_{2}}), v_{i}⟩ = ⟨g^{∗}(u_{i_{3}}), v_{i}⟩ = 1

for some 1 ≤ i_{1}, i_{2}, i_{3} ≤ m, and so, by Lemma 2.1, can be written as v_{i} = (\frac{x_{i}}{D_{i}} , \frac{y_{i}}{D_{i}} , \frac{z_{i}}{D_{i}}), with x_{i}, y_{i}, z_{i}, D_{i} integers of absolute value not exceeding

3 ! (2 · (2n)^{28n^{2}})^{3} < n^{169n^{2}}.

Multiplying this solution by Π_{i=1}^{n}D_{i}, we get the desired embedding of V with all coordinates of all vertices being integers of absolute value not exceeding (n^{169n^{2}})^{n} = n^{169n^{3}}.

Remark. The proofs of Lemma 3.1 and Theorem 1.2 are constructive and provide an algorithm that takes as an input either a rational embedding of a 3-polytope or a 3connected planar graph G (whose faces can be listed by applying an appropriate planaritytesting algorithm to G), and outputs an integral embedding of the polytope which satisfies the bound in Theorem 1.2. Such an algorithm could be used as a preprocessing step to improve robustness of computational geometry algorithms that act on 3-polytopes.

References

[1] J. E. Goodman, R. Pollack, and B. Sturmfels: The intrinsic spread of a configuration in R^{d}. J. Amer. Math. Soc., 3 (1990), 639–651.

[2] B. Grünbaum: Convex Polytopes. John Wiley, New York, 1967.

[3] J.E. Hopcroft and P.J. Kahn: A paradigm for robust geometric algorithms. Algorithmica, 7 (1992), 339–380.

[4] J.C. Maxwell: On reciprocal figures and diagrams of forces. Phil. Mag. Ser. 4, 27 (1864), 250–261.

[5] M. Mignotte: Some useful bounds. In Computer Algebra: Symbolic and Algebraic Computation, eds. B. Buchberger, G. Collins, R. Loos. Springer Verlag, Vienna, 1982.

[6] E. Steinitz: Polyeder und Raumeinteilungen. In Encyclopädie der Mathematischen Wissenschaften. Band 3 (Geometrie) Teil 3AB12 (1922), 1–139.

[7] W. Whiteley: Motions and stresses of projected polyhedra, Structural Topology 7 (1982), 13–38.

[8] H. Whitney: Congruent graphs and the connectivity of graphs. American J. Math., 54 (1932), 150–168.

[9] G.M. Ziegler: Lectures on Polytopes. Manuscript, 1994.

Received 25.3.94