Recovering a point embedding from a graph with edges weighted by point distance

Question

Suppose I give you an undirected graph with weighted edges, and tell you that each node corresponds to a point in 3d space. Whenever there's an edge between two nodes, the weight of the edge is the distance between the points.

Your goal is to reconstruct the relative positions of the points, given only the available distances (represented by the edge weights). For example, if I gave you $d_{0,1} = d_{0,2} = d_{0,3} = d_{1,2} = d_{1,3} = d_{2,3} = 1$, then you know the points are the vertices of a tetrahedron. You don't know where it is relative to the origin, or its orientation, or if it's been mirrored, but you can tell it's a tetrahedron.

In general, the problem is easy if I give you all of the edge lengths. Just arbitrarily pick a point $p_0$ to be at $(0,0,0)$, then pick a neighboring point $p_1$ and place it at $(d_{0,1},0,0)$, then a common neighbor $p_2$ gets triangulated onto the XY plane, then a final common neighbor $p_3$ gets triangulated into the half-space $z > 0$ and breaks the remaining symmetry (assuming you didn't pick degenerate points). You can use those four points to triangulate all the remaining ones.

On the other hand, when some edge lengths are missing it may not be possible to recover the embedding. For example, if there's a vertex that disconnects the graph when cut, then the two components it would separate if removed can swing around relative to each other.

Which raises the questions:

• How expensive is it to find a solution?
• How do you determine if a solution is unique, up to translation/rotation/mirroring? Is 3-connectedness sufficient? Necessary?
• What sorts of conditions make the problem trivial?
• If I don't promise the edge weights actually correspond to point distance sin 3d, how expensive is it to determine if an embedding is possible at all?