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
Computational
Geometry, Gyeongju, South Korea, June 6-8, 2007. Association for
Computing
Machinery, 2007.
Abstract
We present a constructive method for embedding a 3-connected planar
graph with
n vertices as a 3-polytope with small integer coordinates. The
embedding
will need no coordinate greater than O(27.55n).
Finding a plane
embedding
which supports an equilibrium stress is the crucial part in the
construction.
We have to guarantee that the size of the coordinates and the stresses
are
small. This is achieved by extending Tutte's spring embedding method.
Last update: March 27, 2007.