5 Formatting improved

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).
4 Added further constraints to presumably satisfy coordinate algebraic independence; added 2 characters in body

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) - All vertices within a distance $d \leq T$ of one-another share an edge.

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

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

(4) - The minimum degree for each vertex is $\geq 4$ 6$(where the lower-bound connectivity can be adjusted as needed). This implies the two-dimensional graph$G$is at least 4-connected6-connected, requiring and requires the removal of at least four 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) - 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) 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) 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$)? 3 added 10 characters in body; added 22 characters in body 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) - All vertices within a distance$d \leq T$of one-another share an edge. (2) - No vertices separated by a distance$d > T$share an edge. (3) - For any vertex, there is a minimum local density of vertices,$M$, within the threshold connectivity distance$T$. (4) - The minimum degree for each vertex is$\geq 4$(where the lower-bound connectivity can be adjusted as needed). This implies the two-dimensional graph$G$is at least 4-connected, requiring the removal of at least three four edges before the graph becomes to become disconnected. We know from 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) 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\$)?

2 Set the minimum degree of each vertex to '4' from '3'
1