# «Abstract. We discuss two problems in combinatorial geometry. First, given a geometric polyhedral complex in R3 (a family of 3-polytopes attached ...»

Given a d-polyhedron X in Rn and a facet F ∈ X, the Schlegel set of X with respect to F, which we denote by ξ(X, F ), is the closed convex set bounded by the hyperplanes aﬀ(F ) and aﬀ(Gi ) for each facet Gi strongly adjacent to F. That is, if G1,..., Gk ∈ X denote the facets strongly adjacent to F, HGi denotes the closed halfspace bounded by aﬀ(Gi ) and meeting the interior of X, and HF denotes the closed halfspace bounded by aﬀ(F ) and not meeting the interior of X, then ξ(X, F ) = HF ∩ k HGi. A Schlegel point is a point i=1 y ∈ int(ξ(X, F )).

If the facet F is a (d− 1)-simplex, the hyperplanes aﬀ(Gi ) intersect in a (possibly inﬁnite) point, which we call the apex of ξ(X, F ). If the apex x is a ﬁnite point, then x ∈ ξ(X, F ) if and only if x and X lie on opposite sides of the hyperplane aﬀ(F ). If x is a ﬁnite point and x ∈ ξ(X, F ), then ξ(X, F ) is just the cone with base F and apex x.

** Theorem 6.1 Let d ≤ 3 and let X be a topological d-polyhedral complex in Rd such that |X| ∼ B d and all interior facets F ∈ X − ∂X are simplices.**

If X is vertex truncatable, then there is a geometric polyhedral complex Y in Rd such that X ≃ Y. Furthermore, we may choose Y to have all vertices rational.

We prove in fact a stringer result, that such as embedding exists for every given embedding of ∂X. It is important to emphasize that this is a much stronger property, which does not extend to conditions of Theorem 1.4 (see Subsection ??).

Proof. To prove the theorem, we strengthen it, which in turn strengthens our induction

**hypothesis. Namely, we claim that if such a Y exists, then furthermore:**

(i) For any polytope Z such that ∂Z ≃ ∂X, we may choose Y such that |Y | = |Z|.

(ii) Let ǫ 0. Let X1,... Xk ∈ PX such that Xi ∩ Xj ⊆ ∂X and Xi ∩ ∂X is a facet of X, call it Fi. Let Yi ∈ PY be the polyhedron corresponding to Xi and let Gi ∈ ∂Y be the face corresponding to Fi ∈ ∂X. Then we may choose Y such that α(Hj, Gi ) ǫ for all i = 1,..., k and every face Hj ∈ Yi strongly adjacent to Gi.

on the number n of vertices of X. In the base case X has d + 1 vertices, and we may take Y to be any geometric d-simplex in Rd. Now suppose n d + 1.

Since X is vertex truncatable, choose a boundary vertex w0 satisfying either condition (b) or (c) of the deﬁnition. Let X ′ = X ∗ (w0 ) w0. By deﬁnition, X ′ is vertex truncatable, so in particular |X ′ | ∼ B d. Furthermore, all interior facets of X ′ are clearly simplices.

Let Z be a polytope such that ∂Z ≃ ∂X. If d = 3, such a polytope Z exists by Steinitz’s Theorem. If d = 2 then Z may be any strictly convex polygon with the same number of boundary vertices as X. Since w0 is boundary minimal, it has d neighbors w1,..., wd in ∂X. Let v0 denote the vertex of Z corresponding to w0. For each i = 1,..., d, the vertex wi corresponds to a vertex vi of Z, where vi is a neighbor of v0. The vertices vi lie on a hyperplane H = aﬀ(v1,..., vd ). The hyperplane H splits Z into two polytopes Q1, Q2, each deﬁned by taking all faces of Z lying on a given side of H, which includes the facet TZ = conv(v1,..., vd ) in both cases. One of these two polytopes, say Q1, contains v0. Then note that Q1 is a d-simplex.

Clearly |lkX ∗ (w0 ) (w0 )| is homeomorphic to a (d − 1)-ball. So if d = 3 then lkX ∗ (w0 ) (w0 ) is isomorphic to the Schlegel diagram of some 3-polytope by Steinitz’s theorem. Call this polytope A. If d = 2 then we may simply take A to be a convex polygon with one more edge than lkX ∗ (w0 ) (w0 ). Let u1,..., ud be the vertices of A corresponding to the vertices v1,..., vd of lkX ∗ (w0 ) (w0 ), and let TA = conv(u1,..., ud ). Note that TA is a (d − 1)-simplex, and a facet of A. Apply an aﬃne transformation to |A| so that TA = TZ. If A is not a simplex, apply a projective transformation to |A| that ﬁxes TA and takes the apex x of ξ(A, TA ) to a ﬁnite point on the side of the hyperplane aﬀ(TA ) not containing |A|.

For a set S ⊆ Rd, let (S, 1) = {(x, 1) ∈ Rd × R | x ∈ S}. Form the (d + 1)-cone C with base (|A|, 1) and apex a ∈ Rd+1, ad+1 = 1. Let FC denote the (clearly simplicial) d-face of C containing a and (TA, 1). Let W denote the Schegel projection of C onto its facet FC, with respect to a Schlegel point y. Then W is a geometric polyhedral complex. Clearly W contains a subcomplex B such that B ≃ A. Since (TA, 1) ⊆ FC, the (d − 1)-face (TA, 1) is ﬁxed by the Schlegel projection, so in fact (TA, 1) ∈ B is the face of B corresponding to TA ∈ A. Apply an aﬃne transformation to |W | that maps (TA, 1) to TA = TZ and maps a to v0. This transforms |B| accordingly. In particular, we now have |W | = |Q1 |. Thus Z ′ = B#TZ Q2 is a polytope such that ∂Z ′ ≃ ∂X ′.

By the induction hypothesis and (i), since X ′ contains one fewer vertex than X, there is a geometric polyhedral complex Y ′ such that X ′ ≃ Y ′ and |Y ′ | = |Z ′ |. Let Y ∗ = Y ′ ∪ W.

Then clearly X ∗ (w0 ) ≃ Y ∗. Removing the facets of Y ∗ corresponding to the facets τ (w0, P ) of X ∗ (w0 ), we obtain a polyhedral complex Y such that X ≃ Y and |Y | = |Z|. This establishes (i), provided that each cell of Y is convex. We now show that this is the case.

Let X1,..., Xk ∈ PX ′ denote the d-polyhedra of X ′ such that |Xi′ | ⊆ |X| for some ′ ′ X ∈ PX (w0 ). We will let Xi denote the unique d-polyhedron of X such that |Xi′ | ⊆ |Xi |.

For all i, j = 1,..., k, since w0 ∈ Xi ∩ Xj and X is a polyhedral complex, we must have Xi′ ∩ Xj ⊆ ∂X ′, for otherwise Xi and Xj would intersect in more than a unique common ′ face. If w0 is a strong solitary vertex of X, then k = 1. Thus the single polyhedron Y1 ∈ PY corresponding to X1 is clearly convex from the above construction.

Now suppose that w0 is a strong shedding vertex of X. Note that any shedding vertex w0 of X must satisfy cstX (w0 ) ∩ ∂X = cst∂X (w0 ), for otherwise |X w0 | would not be homeomorphic to B d. Thus we must have Xi′ ∩ ∂X ′ = τ (w0, Xi ). So X1,... Xk satisfy ′ ′ the hypotheses of (ii). Let Yi′ ∈ PY ′ be the polyhedron corresponding to Xi′ and Gi ∈ Y ′ the facet corresponding to τ (w0, Xi ). Let Yi ∈ PY be the unique polyhedron such that |Yi′ | ⊆ |Yi |. Since our induction hypothesis is enhanced by (ii), we may assume that the 22 IGOR PAK, STEDMAN WILSON angles α(Hj, Gi ) are arbitrarily small for each i and each face Hj ∈ Yi′ strongly adjacent to Gi. Since the cells |Yi′ | are convex by induction and form arbitrarily small angles with Gi, we may ensure that on removing Gi the resulting cell |Yi | ∈ Y is convex. Finally, if σ ∈ Y is a cell not having any of the |Yi′ | as a subset, then either σ is a d-simplex (hence convex) or σ ∈ Y ′. In the latter case σ is convex because Y ′ is a geometric polyhedral complex.

Now we must show that (ii) holds. Let X1,..., Xℓ ∈ PX be a collection of polytopes satisfying the hypotheses of (ii), and let Y1,... Yℓ ∈ PY denote the corresponding polytopes of Y. If Yi ∈ PY ′ then we obtain the conclusion of (ii) from the induction hypothesis.

Now suppose Yi ∈ PY ′. Then Yi ∈ PW. If the A in the above construction is a simplex, / then ℓ = 1. Let v be the vertex of A not contained in TA. Then we may clearly choose v arbitrarily close to the facet Yi ∩ ∂Y. If A is not a simplex, then because the point x is ﬁnite and lies on the side of aﬀ(TA ) opposite to that of A, x ∈ ξ(C, FC ). In particular ξ(C, FC ) is a cone with base FC and apex x ∈ Rd+1. By choosing the Schlegel point y in the above construction arbitrarily close to x, we may ensure that all such angles α(Fi, Fj ) in the projection W are arbitrarily small.

Finally, that Y may be chosen to be rational is an immediate consequence of the methods of the proof. Broadly speaking, we obtained Y by ﬁrst using Steinitz’s theorem to produce polytopes Z and A, and then manipulating these polytopes using projective transformations.

But from the proof of Steinitz’s theorem, we may take both Z and A to be rational. By then using only rational aﬃne and projective transformations in the above constructions, we may in fact obtain a rational geometric polyhedral complex Y such that X ≃ Y.

It is straightforward to show that all 2-polyhedral complexes are vertex truncatable. Thus Theorem 6.1 implies that all 2-polyhedral complexes are geometrically realizable. Note that every 2-polyhedral complex is a 2-connected plane graph. However, the converse is not true.

In fact, if a 2-connected plane graph is not a polyhedral complex (i.e. if the intersection of two faces is more than a unique common edge or vertex of both), then it clearly does not admit an embedding such that all faces are strictly convex.

Therefore we obtain necessary and suﬃcient conditions for a 2-connected plane graph G to admit an isotopic embedding G′ such that all faces of G′ are strictly convex. Speciﬁcally, a 2-connected plane graph G has a strictly convex isotopic embedding if and only if G is a 2-polyhedral complex. From this we recover Tutte’s theorem [T1].

Finally, we note that the condition d ≤ 3 in the statement of Theorem 6.1 plays a crucial role. Namely, it allows us to invoke Steinitz’s theorem (for d = 3). For example, by Steinitz’s theorem a simplicial 2-sphere is always isomorphic to the boundary of a 3-polytope. In higher dimensions the analogous statement is not true (see [GS]).

7. Further discussion

7.1. It is perhaps not obvious why Theorem 1.1 does not follow from existence of irrational 4-polytopes. Indeed, one can take a Schlegel diagram Q of an irrational 4-polytope P and conjecture that this is the desired irrational polyhedral complex. The logical fallacy here is that the implications go the other way. If the Schlegel diagram of P is irrational, then indeed P must be an irrational polytope. However, the converse is not true. There is no reason why all realizations of the Schegel diagram Q must have irrational coordinates, even if P is irrational. In fact, after computing degrees of freedom one should expect additional realizations of Q. Similarly, it is only in R3 that one can have (and does have) the MaxwellCremona theorem [R]; in R4 and higher dimensions it easily fails in full generality (cf. ??).

## GEOMETRIC REALIZATIONS OF POLYHEDRAL COMPLEXES 23

On the other hand, it was noted by Richter-Gebert [?, §10] that the polytope operations used in the construction of irrational polytopes can be emulated in R3 by an analogous operations on the level of Schegel diagram.1 Richter-Gebert brieﬂy outlined both an irrational construction and a universality type theorem. If completed, the former construction would prove smaller than out 1278 polytope construction in Theorem 1.1, but each polytope is more complicated. The latter (universality result), is of a diﬀerent nature from Theorem 5.5 as no intersections are allowed. As stated, it would imply only the ﬁrst part of Theorem 5.2 (and only if the outside face is a tetrahedron), since we allow only triangular prisms as our polyhedra.7.2. Let us here address a delicate issue of Brehm’s universality theorem, as outlined in [Br, Z2]. Our Theorem 5.5 is clearly a variation on Brehm’s announced result. In fact, the proof ideas do not seem very far from ours, even if diﬀerent on a technical level. Unfortunately, the Brehm’s complete proof has never appeared, and from our experience with universality type theorems these details are occasionally delicate and important. Thus, one can view our work as either an application of our tools to re-derive Brehm’s results, or the ﬁrst complete proof of a theorem of this type. Since in fact our construction has further properties is an unexpected bonus.

Let us mention that allowing intersections in our proof of Theorem 5.5 as the belts can get linked and knotted in a non-trivial way, a possibility we cannot account without further sub-triangulating the construction.

7.3. There is a rather simple reason why Tutte’s theorems are delicate and unlikely to allow a direct extension to higher dimensions, even ignoring the topological obstructions as in the paper. Consider the ﬁrst two graphs as in Figure 11 below. The smaller of the two has a non-strict convex realization, while the bigger does not. Tutte’s result is “if and only if”, and he explains that the diﬀerence between the two is a combinatorial rather than geometric or topological reason. Now of course, neither have a (strict) convex realization.

This can be explained from the fact that this graph is not 3-connected and thus its spring embedding collapses. But in R3 if one replaces the middle square with an octahedron, the connectivity obstacle disappears.

7.4. The vertex truncatability condition in Theorem 1.4 is somewhat restrictive already in R3. For example, it cannot apply to any triangulation of the octahedron or the icosahedron since their boundaries have no vertices of degree three.

Recall now that the inductive assumption in the proof of Theorem 1.4 implied that the boundary can be prescribed in advance. Now the study of triangulations of the octahedron shows that vertex truncatability is critical for the result. Consider an octahedron Q = (11′ 22′ 33′ ) with topological triangulation (122′ 3), (122′ 3′ ), (1′ 233′ ), (1′ 2′ 33′ ), and (22′ 33′ ).

In this triangulation, the triangles (122′ ) and (1′ 33′ ) are not linked (topologically). But this is false for some realizations of Q. This means that Theorem 1.4, at least a stronger version where the boundary is prescribed, cannot possibly be extended to triangulations as simple as this one.

Interestingly, one can easily see why the “linked triangle obstacles” never appears in our situation. That is because the vertex truncatability condition forbids all diagonals, deﬁned as inner edges connecting two boundary vertices. This follows easily by induction.

Finally, let us mention that we do not believe that Theorem 1.4 extends to d ≥ 4. It would be interesting to ﬁnd such a counterexample.

7.5. It is obvious that the triangulation produced in Theorem 1.4 can be made rational: