Determine if a graph with partial 2D distances has a ~single embedding in $R^2$

Question

I've stumbled upon an interesting topic, and am wondering if any relevant formal
research took place, perhaps under different terminology than mine.

Definition

Looking at a graph G=(V,E) with weighted-edges indicating known distances between vertices,
where not all distances are known - a (partial) distance-graph,
define it to be "stable" if there exists at least one valid embedding of the vertices
in $R^2$, and any two valid embeddings are the same up to rotations, translations
and mirroring along an arbitrary axis.
Going forward, assume there's always at least one valid embedding.

Claim

The following are equivalent, assuming there is at least one set of three vertices holding the assumption in (3):

1. G is stable.
2. We can calculate the distance between any two vertices based on the known distances, regardless of any embedding.
3. We can determine all vertices' positions in $R^2$ given the positions of any three of them which are not on the same line and have known distances between them.

Examples

In the following examples, the vertices are embeddable in their depicted locations in $R^2$, and the edge-lengths stem from those locations.

For starters, consider (pardon my ascii):

v1 --------------- v2
 | |                |
 |    |             |
 |       |          |
 |          |       |
 |             |    |
 |                | |
v3 --------------- v4

This graph isn't stable, as v3 can be mirrored along the v1->v4 axis (the same goes for v2). Adding the v2->v3 edge stabilizes the graph, but that's a trivially-stable graph (all edges are known, so (2) holds by definition).

For a non-trivial example, consider:

    v1 ----- v2
   |  |       | |
  |    |     |   |
 |     |     |    |
v3 -------------- v5
   |    |   |    |  
     |  |   |  |
       | | | |
          v4

One can prove that this graph holds (3), although it doesn't supply all possible edges.
Replace (v3, v5) with (v1, v5) and this will no longer be the case, as v3 could be mirrored along the v1->v4 axis. (In general, any vertex with 2 or less neighbors breaks stability.)

Proving the equivalences, if you're interested:

Given (2) and three positioned vertices, use triangulation to find all others - (2) implies (3).

Given (3) and two valid embeddings, find the single
affine linear transform from the known vertices
as mapped in embedding 1 to their positions in embedding 2.
Apply the transform to all vertex-locations in embedding 1 to get a new, valid embedding.
From the assumption, this new embedding should be the same as embedding 2.
(3) implies (1).

Given (1), take an arbitrary embedding and calculate all distances,
any embedding yields the same results, (1) implies (2).

Question

The main question is, how does one determine algorithmically whether or not
a partial distance-graph is stable?
I've devised a gradient-descent-based algorithm for estimating locations given a distance-graph
and a few known points (again, is there a known method for doing this which I am unaware of?),
so a simple heuristic would be to set fixed locations for three points with known distances
between them, run the algo a few times with random initial guesses,
and see if G.D. converges each time to the same locations
(when it indeed converges to the same minimum price) -
giving a strong indication of a single embedding.
However, I'm looking for some provable criteria, if one is already known -
perhaps from other fields like construction/architecture.

Answer 1

This falls under "rigidity theory", and is specifically categorized as "global rigidity". To simplify analyzing the problem, and avoid rigidity classifications which are highly-dependent of the exact edge lengths given (as noise should be taken into account), we discuss "generic global rigidity" instead, which considers the graph's structure and "well-behaved" edge-lengths, ignoring any given edge lengths.

Google's results for "rigidity theory" might not be what you want - a lecture MIT published on generic local rigidity, which is a solved problem specifically in $R^2$: https://www.youtube.com/watch?v=k2jKCJ8fhj0

Google's useful result for "global rigidity": https://www.cs.harvard.edu/~sjg/papers/ggr.pdf ("CHARACTERIZING GENERIC GLOBAL RIGIDITY" by Gortler, Healy & Thurston, 2007.)

a generic framework is globally rigid if and only if it has a stress matrix with kernel of dimension d + 1, the minimum possible. [...] We also show that this condition is efficiently checkable with a randomized algorithm

As for finding an approximate embedding in $R^2$, as pointed out by @ElchananSolomon in the question's comments, we use MDS.

Answer 2

This question can be rephrased as "when can an abstract metric space be embedded in $\mathbb{R}^d$?" (for $d=2$, in your case). This is a well-studied question.

The most useful place to look is the Wikipedia page on Euclidean distance matrices. There you will find the Schoenberg criterion, which is an if and only if characterization of Euclidean embeddability. I'll summarize it here:

1. Let $D$ be the matrix of distances.
2. We need the diagonal of $D$ to be zero (this is called being hollow), as will always be the case for your graphs.
3. The entries of $D$ must be real numbers, which again will always be the case for your graphs.
4. You need to turn $D$ into the Gram-matrix $G$ using the formula $G_{ij} = \frac{1}{2}(D_{1i} + D_{1j} - D_{ij})$. The Gram matrix can be interpreted as containing dot-product, rather than distance, information.
5. If $G$ is positive semi-definite and has rank at most $k$, the metric space can be embedded into $\mathbb{R}^k$.
6. To find the embedding, we assume $G = X^{T}X$, where $X$ is the matrix containing the embedding coordinates. This formula indeed asserts that $G$ consists of dot products. The question then becomes: how to compute $X$ given $G = X^{T}X$? What we do is perform an eigen-decomposition of the symmetric matrix $G = U \Lambda U^{T}$. Since $G$ is positive semi-definite, the entries of the diagonal matrix $\Lambda$ are positive, so it makes sense to define $\sqrt{\Lambda}$. Then if we set $X = \sqrt{\Lambda}U^{T}$, we see that $X^{T}X = U\sqrt{\Lambda}\sqrt{\Lambda}U^{T} = U \Lambda U^{T} = G$, satisfying the necessary equation. Thus $\sqrt{\Lambda}U^{T}$ contains the vectors of the desired Euclidean embedding.