Rigid realizations of graphs on small grids

摘要

A framework (G, p) is a straight line realization of a graph G = (V, E) in R-2, given by a map p: V -> R-2. 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 is an element of V (G), are distinct points of the k x k grid, where k = [root vertical bar V vertical bar - 1] + 9. We also show that such a framework on G can be constructed in O(vertical bar V vertical bar(3)) time. (c) 2005 Elsevier B.V. All rights reserved.