**Abstract:**
This paper answers the following question: Given an ``erector set''
linkage, a connected set of fixed-length links, what is the minimal
e needed to adjust the edge lengths so that the vertices of the
linkage can be placed on integer lattice points? Each edge length is
allowed to change by at most e. Angles are not fixed, but
collinearity must be preserved (although the introduction of new
collinearities is allowed). We show that the question of determining
whether a linkage can be embedded on the integer lattice is strongly
NP-complete. Indeed, we show that even with e = 0 (under
which the problem becomes ``Can this linkage be embedded?''), the problem
remains strongly NP-complete. However for some applications, it is
reasonable to assume that lengths of the links and the number of
``co-incident'' cycles are bounded (two cycles are co-incident if they
share an edge). We show that under these bounding assumptions, there is a
polynomial time solution to the problem.

Recent Publications of Neil Immerman