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.


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.
  PostScript file (gzipped)   pdf file
other papers about this subject
Last update: March 27, 2007.