Hendrickson, Bruce A.2007-04-232007-04-231988-11http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR88-950https://hdl.handle.net/1813/6790The graph embedding problem is that of computing the relative locations of a set of vertices placed in Euclidean space relying only upon some set of inter-vertex distance measurements. This paper is concerned with the closely related problem of determining whether or not a graph has a unique embedding. Both these problems are NP-hard, but the proofs rely upon special combinations of edge lengths. If we assume the edge lengths are unrelated then the uniqueness question can be approached from a purely graph theoretic framework that ignores edge lenghts. This paper identifies three necessary graph theoretic conditions for a graph to have a unique embedding in any dimension. Efficient sequential and NC algorithms are presented for each condition, although these algorithms have very different flavors in different dimensions.2540462 bytes536736 bytesapplication/pdfapplication/postscripten-UScomputer sciencetechnical reporttechnical report