Question

Consider the two-dimensional non-planar graph $G$, with known topology and edge lengths $(r_1, r_2, ... r_N) \in R$, but unknown vertex coordinates. We further specify that:

(1) -

1. All vertices within a distance $d \leq T$ of one-another share an edge.

   (2) -

2. No vertices separated by a distance $d > T$ share an edge.

   (3) -

3. For any vertex, there is a minimum local density of vertices, $M$, within the threshold connectivity distance $T$.

   (4) -

4. The minimum degree for each vertex is $\geq 6$ (where the lower-bound connectivity can be adjusted as needed). This implies the two-dimensional graph $G$ is at least 6-connected, and requires the removal of at least six edges to become disconnected.

   Note: A big thank you to JC for point out the corollary in [Jackson and Jordán, 2005] that: "...every realization of a 6-connected graph as a two-dimensional generic framework is a unique realization."

   (5) -

5. The set $S$ of real-valued vertex coordinates for $G$ are sequentially chosen with uniform random probability across some interval under the constraint that no coordinates may be within a small fixed distance, $\tau$, of one-another. This should imply that coordinates are algebraically independent.

We know from Saxe(1) Saxe 1 that, like the graph realization problem, the generalized problem of deciding if a unique solution exists for the graph realization problem in two-dimensional (and higher-dimensional) space is NP-hard. However, these proofs rely on graphs with certain pathological properties (2).

1. Saxe, J.B. Embeddability of weighted graphs in k-space is strongly NP-hard. Tech. Report, Computer Science Department, Carnegie-Mellon University, Pittsburgh, PA (1979).

2. Hendrickson, B. Conditions for unique graph realizations. SIAM J. Comput. 21, pp. 65-84 (1992). (which can be found here - http://www.cs.duke.edu/brd/Teaching/Bio/asmb/current/Readings3/hendrickson-conditions.pdf)[2].

   Provided the above description of $G$, are there any heuristics or further restraints that would allow me to say with some confidence that $G$ is rigid? Pressing my luck, are there are polynomial-time algorithms for solving the graph realization problem for $G$, i.e. using the set of edge lengths $R$ to find coordinates for each of the vertices (possibly allowing for some error, $\epsilon$)?

   References:

   1. Saxe, J.B. Embeddability of weighted graphs in k-space is strongly NP-hard. Tech. Report, Computer Science Department, Carnegie-Mellon University, Pittsburgh, PA (1979).
   2. Hendrickson, B. Conditions for unique graph realizations. SIAM J. Comput. 21, pp. 65-84 (1992).