Return to 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. 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 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. 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].

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).

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 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. 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].

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).

(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 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.

(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$)?

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 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.

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].

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).

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 four edges 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$)?

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 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) - 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$)?