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](http://www.cs.duke.edu/brd/Teaching/Bio/asmb/current/Readings3/hendrickson-conditions.pdf) 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*](http://www.cs.duke.edu/brd/Teaching/Bio/asmb/current/Readings3/hendrickson-conditions.pdf). SIAM J. Comput. 21, pp. 65-84 (1992).



Is the following two-dimensional graph likely to be globally rigid?
I'm not sure how to make a real answer out of this, since you're interested in a situation where the edge lengths are given and not the positions of vertices. But -- *generic* global rigidity is a property just of the graph $G$ (generic global rigidity means global rigidity for any embedding of the graph where the positions of the vertices are algebraically independent over the integers).


If your edge lengths are generic in some sense, then there might be a way of arguing that your vertex embeddings should be generic too (*Caution! This is the part that my thinking is unclear / nonexistent on*), and then you could check the global rigidity by just thinking about the topology of the graph G: The discussion in Hendrickson's paper states the condition that a 2D graph has an "infinitesimally redundantly rigid" realization is a necessary condition for generic global rigidity. This is actually a sufficient condition as well, due to work of [Jackson and Jordán](http://dx.doi.org/10.1016/j.jctb.2004.11.002).


So you can check whether a graph G is generically globally rigid in 2D by removing each of its edges and running the ["pebble game" algorithm of Jacobs and Hendrickson](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.8756&rep=rep1&type=pdf) on the resulting graph -- if the pebble game says that each one of those graphs is generically (locally, i.e. infinitesimally) rigid then the original graph G was generically globally rigid.


The abstract of Jackson and Jordán's paper also contains:



> 
> As a corollary we deduce that every realization of a 6-connected graph as a two-dimensional generic framework is a unique realization.
> 
> 
> 


which might be a useful fact to you as well, given your point (4).


Let me add that I wrote [an answer on a different but related question](https://mathoverflow.net/questions/47181/can-we-uniquely-define-a-graph-to-have-the-topology-of-a-polytope-via-proper-edge/47467#47467) in which you might find some other interesting references. In particular, a lot of what I wrote above I learned from some of the introduction to [Gortler, Healy and Thurston's paper](http://arxiv.org/abs/0710.0926) on generic global rigidity in higher dimensions, which gives a nice overview of a lot of the work on these problems.




---


**Edit**: Some discussion of genericity, addressing the comments follows:


In (5), the reason that you almost surely will have a generic framework is because the set of non-generic vertices is not dense in the set of all possible choices of vertices that you're choosing from. It's a bit like choosing uniformly at random a number from the unit interval and asking if it's an algebraic number. 



> 
> What if I said I was going to randomly and densely place vertices in cells of a finite matrix?
> 
> 
> 


In this situation, which I think is effectively the same as choosing your vertices to have bounded integer coordinates (i.e. choosing from an integer grid), instead of zero probability that you will have some relation between the coordinates of the vertices, you will *always* have algebraic (rational, even) relations between the coordinates of the vertices.


However, not all is lost. I think that all that the "no algebraic relations at all between vertices" definition of genericity is doing here is actually just making sure that the vertices lie away from those algebraic relations which are defined by the minors of the rigidity matrix (see e.g. [the discussion on pages 21 and 22 in Graver, Servatius and Servatius's book](http://books.google.com/books?id=0XwvY1GVNN4C&lpg=PP2&ots=2CSHFZH_vT&dq=combinatorial%20rigidity&pg=PA21#v=onepage&q&f=false) ) or see sections 3 and 4 in [Connelly's paper Generic Global Rigidity](http://www.math.cornell.edu/~connelly/global-6.pdf) to see how genericity is actually used in these theorems. So, in some sense that definition is a bit of overkill -- instead of avoiding every algebraic relation, you just have to avoid those coming from the rigidity matrix. I won't give a definition of the rigidity matrix (sometimes "stress matrix") here -- you can find it in most of the papers on rigidity that I've cited.


So, if you choose the vertices randomly with bounded integer coordinates, you will have a finite probability of getting an embedding which is non-generic in the sense that one or more of the minors of the rigidity matrix defined by the graph happen to vanish - note that these are the cases where the rigidity behavior of the embedding will differ from the generic embedding predictions for your graph. Roughly speaking, the locus of positions of vertices which satisfy some relation coming from the rigidity matrix (which is all that matters for rigidity properties) is going to be an intersection of lower dimensional algebraic curves in the full space. 


If you're choosing the coordinates from a large enough set of integers (or equivalently, if your "matrix" is dense enough in the region of space you're approximating with it), the probability of such non-generic behavior should be small enough that you don't have to worry about it. When your matrix is really big, most of the vertex positions will avoid the "bad" subset and the generic rigidity predictions will coincide with the actual behavior. Don't ask me to give explicit estimates though...


All of the above is kind of artificial though. Remember that if you just perturb the positions of each of the coordinates of your vertices each by some tiny incommensurate transcendental numbers, your embedding will be generic in the original sense no matter what you started with. You might even say that any "physical" graph will always be embedded generically because there's no way to place perfectly commensurate vertices or edges. I guess what could go bad when you are very close to a non-generic embedding is that you have some different "approximate" embeddings with edge lengths very close to those of your original graph.


I'm just learning most of this stuff myself, so I think I would recommend you to spend some time understanding the papers and making sure that what I said is right too.


