One of the main area of research are grid embeddings of convex 3d polytopes. By Steinitz' theorem every 3-connected planar graph can be embedded as a convex 3d polytope, even with integer coordinates. The question is, how large have the coordinates to be, in terms of the number of the vertices . Although there were a series of improvements over the grid size of Steinitz' construction (of course he was not interested in getting integer or even small coordinates) the current best algorithm uses coordinates of size . At least for triangulations (simplicial polytopes) I expect however that the necessary grid size is bounded by a polynomial. In fact, the current lower bound is only .

This post is about embedding a very special graph as a convex 3d polytope: the graph of the dodecahedron. In other words, what is the smallest grid in which one can embed a (nonregular) dodecahedron. The dodecahedron is interesting since it is the smallest example with no triangular and quadrilateral faces. This seems to be a more tricky case, at least for the current best algorithm that would embed the dodecahedron on the grid with z-coordinates ranging between zero and 11 083 163 098 782 678 334 820 352. Of course we can do better. Francisco Santos found an embedding that fits inside the 8 x 6 x 4 grid. Also, there is a very symmetric realization known as pyritohedron that needs a 12 x 12 x 12 grid.

I was wandering if this is the best we can get. That's why I asked Finn Nielsen, a student of mine, to search for a smaller realization. We did a computer search and found indeed a smaller realization. It uses only a grid of size 4 x 4 x 4. This embedding seems very natural and simple. We also know that it is the smallest possible embedding in terms of volume (Francisco Santos found another embedding on the 3 x 12 x 12 grid). The search space seems quite huge, but if one constructs the embedding vertex by vertex, then there are a lot of constraints, especially for the dodecahedron, and the search can be done quite fast.

We are going to present this work (among other results) as a poster at the Graph Drawing conference in Bordeaux next week.