Abstract. The graph realization 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 realization. Both these problems are NP-hard, but the proofs rely upon special combinations of edge lengths. If we assume the vertex locations are unrelated then the uniqueness question can be approached from a purely graph theoretic angle that ignores edge lengths. This paper identi es three necessary graph theoretic conditions for a graph to have a unique realization in any dimension. E cient sequential and NC algorithms are presented for each condition, although these algorithms have very di erent avors in di erent dimensions.
A work of Hendrickson relates the EDM completion problem to a graph realization problem and provides necessary graph theoretic conditions on the partial matrix that ensures a unique solution REF .
Conditions for Unique Graph Realizations
SIAM J. Comput.
Mathematics Computer Science