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

1. Embedding 3-polytopes on a small grid

2. Small grid embeddings of 3-polytopes

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(2^7.55n)=O(188ⁿ). 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.