Ares Ribó Mor, Günter Rote, and André Schulz:

1. Embedding 3-polytopes on a small grid

In: Proceedings of the 23rd Annual Symposium on Computational Geometry, Gyeongju, South Korea, June 6–8, 2007. Association for Computing Machinery, 2007, pp. 112–118. doi:10.1145/1247069.1247086

2. Small grid embeddings of 3-polytopes

Discrete and Computational Geometry 45 (2011), 65–87. doi:10.1007/s00454-010-9301-0, arXiv:0908.0488 [cs.CG].


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)=O(188n). Finding a plane embedding which supports an equilibrium stress is the crucial part in the construction. In order to guarantee that the size of the coordinates and the stresses are small, we extend Tutte's spring embedding method.

  pdf file (gzipped)   free PDF view@Springer
other papers about this subject
Last update: August 15, 2017.