Rigid realizations of graphs on small grids

A framework (G,p) is a straight line realization of a graph G=(V,E) in R2, given by a map p:V→R2. We prove that if (G,p) is an infinitesimally rigid framework then there is an infinitesimally rigid framework (G,q) for which the points q(v), v∈V(G), are distinct points of the k×k grid, where k=⌈|V|−1⌉+9. We also show that such a framework on G can be constructed in O(|V|3) time.