Embedding stacked polytopes on a polynomial-size grid (Q2358818)

A well-known theorem of Steinitz states that planar \(3\)-connected graphs are exactly the graphs of \(3\)-dimensional polytopes. In the proof of the theorem, Steinitz uses a given graph to construct a polytope whose vertices can be embedded as triples of integers. The construction results in vertices whose coordinates are doubly exponential in the number of vertices. Since then, there has been a significant amount of work in constructing a \(3\)-polytope from a \(3\)-connected graph with lower bounds on the coordinates of the vertices. The article under review provides an algorithm for realizing a special class of \(d\)-polytopes with \(n\) vertices in integer grids whose dimensions are polynomial in \(n\), improving the best-known bound for arbitrary \(d\)-polytopes. The special class is that of \textit{stacked polytopes}: let \(P\) be a \(d\)-dimensional polytope with \(n\) vertices and at least once simplicial facet \(F\). A \textit{stacking operation} on \(P\) glues a simplex \(\Delta\) onto \(P\) by identifying a facet of \(\Delta\) with \(F\), so long as the resulting geometric body is still convex. Call \(P\) \textit{stacked} if it can be obtained by applying a sequence of stacking operations to a \(d\)-simplex. The main theorem specifically notes that the integer coordinates in the embedding constructe have size at most \(10d^2R^2\) except for one axis, where the bound is \(6R^3\), where \(R = dn^{\log(2d)}\). The authors provide a brief but very nice history of the improvements made to the original construction of Steinitz. They note that the standard two-stage approach (specifying stress and computing the barycentric embedding) for improving the bound for \(3\)-polytopes does not extend to \(d\)-polytopes easily; hence, they must modify the approach for stacked polytopes. To prevent large coordinates in the embedding, the authors use \textit{heavy path decomposition}, a technique borrowed from data structural analysis. The vertices of the lifted flat embedding therefore have a controlled size, but are not yet necessarily integers; analyzing the size of the feasible perturbations of the vertices allows the coordinates to be rounded to a polynomial-sized grid without breaking the combinatorial structure of the polytope.