Ares Ribó Mor, Günter Rote, and André Schulz:
Embedding 3-polytopes on a small grid
to appear in: Proceedings of the 23rd Annual Symposium on
Geometry, Gyeongju, South Korea, June 6-8, 2007. Association for
We present a constructive method for embedding a 3-connected planar
n vertices as a 3-polytope with small integer coordinates. The
will need no coordinate greater than O(27.55n).
Finding a plane
which supports an equilibrium stress is the crucial part in the
We have to guarantee that the size of the coordinates and the stresses
small. This is achieved by extending Tutte's spring embedding method.
Last update: March 27, 2007.