UCLA

When does a topological polyhedral complex (embedded in R^d) admit a geometric realization (a rectilinear embedding in R^d)? What are the constraints on the possible realizations? Two classic results concerning such questions are Fary's theorem, which states that every planar graph can be drawn in the plane such that each edge is a straight line segment, and Tutte's theorem, which provides necessary and sufficient conditions for embedding a planar graph such that all faces are convex. The present work is motivated largely by the question of whether these types of results generalize to higher dimensions.

We begin by constructing an irrational polytopal complex consisting of 1278 convex 3-polytopes in R³. The methods of this construction may also be used to produce small topological complexes with no geometric realization, as well as geometric complexes which encode arbitrary point and line configurations. This allows us to prove universality theorems for 3-dimensional polytopal complexes and arrangements. We also investigate geometric realizations of plane triangulations, and describe an explicit algorithm that embeds a plane triangulation with n vertices in a 4n³ x 8n⁵ integer grid, in such a way that at each step of the algorithm, the resulting region of the plane is convex. This embedding, by nature of its sequential convexity, may be lifted vertically to a 3-polytope. This process gives a new proof of Steinitz's Theorem for triangulations, and provides a new upper bound on the size of the integer grid necessary to embed the vertices of simplicial 3-polytopes. For certain classes of triangulations, this grid size is subexponential.