Is the following two-dimensional graph likely to be globally rigid?

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

Answer 1

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.

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 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 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 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 ) or see sections 3 and 4 in Connelly's paper Generic Global Rigidity 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.

Answer 2

(this should be a comment, but I have no such privileges)
@jc: You are correct, that, by genericity, all one is really trying to do, is avoid a few specific bad algebraic subsets. The main ones to avoid are places where the rigidity matrix, or the stress matrix has a "less than maximal rank". There is also one more bad subset that needs to be avoided: non-smooth points of the so-called "measurement set" where it self intersects. At such points, global rigidity can be lost. Avoiding such places is needed in Connelly's sufficiency proof. See Example 8.1 in Connelly and Whiteley's "Global Rigidity: The effect of coning" for an example where this subset is hit.

Answer 3

Note that condions 1 and 2 define a so called "unit-disk" graph. Even in this case, finding an embedding from distances is still NP-HARD. (see "A Theory of Network Localization" by Aspnes et al.) Though, as Dylan just explained, when the graph is "dense" enough to be universally rigid, then there is an efficient algorithm for (approximate) localization.

Answer 4

jc's answer touches most of the bases. Let me just clear up a few points.

You can, in fact, give concrete bounds on the probability a graph with vertices chosen from a finite grid will fail to be generic for the purposes of rigidity, as jc alluded to. The relevant theorem is called the Schwartz-Zippel(-DeMillo-Lipton) Lemma. Namely, suppose you are given a non-zero polynomial $P(x_1,\dots,x_n)$ of degree $d$ over some field $F$, and a finite subset $S$ of $F$. Then the probability that $P$ is zero when evaluated on arguments chosen uniformly at random from $S$ is zero at most $d/|S|$. This gives an easy randomized algorithm for testing whether a polynomial is zero or not, given bounds on the degree. (Lipton wrote up a nice history.)

The test for local rigidity boils down to checking the rank of the rigidity matrix (the Jacobian of the length function), which can in turn be interpreted as checking whether a certain polynomial is zero. Concretely, in my paper Characterizing Generic Global Rigidity with Healy and Gortler (published version) we go through the analysis and get specific bounds (in Section 5). We also go through some analysis for global rigidity, but it's for whether the check for generic global rigidity works, not whether the particular framework is actually globally rigid. For concrete bounds there, you'd have to do a little more work.

(While I was writing this, my co-author Steven Gortler posted his own answer, but we cover different points so I'm leaving this up.)

I think the question about global rigidity is well-answered by now. The question also asked about algorithms for finding the realization. It sounds like the graphs are pretty dense, dense enough that they're likely to be universally rigid: the edge lengths will determine the positions in any dimension, not just 2 dimensions. (For instance, the square of any 3-connected graph is 3-connected, see On affine rigidity, published version.) For such graphs, there is a good algorithm, namely semidefinite programming: Consider the Gram matrix of the configuration, the positive semi-definite matrix formed by dot products between the coordinates. The length constraints give linear constraints on such matrices. If the graph is universally rigid, there will be essentially one PSD matrix satisfying the constraints; this gives you the embedding. This kind of problem (a PSD matrix with linear constraints) can be solved quickly, at least in practice.

Answer 5

Your condition (1) is very close to guaranteeing that the graph is a triangulation, so is very likely to be globally rigid. For (much) more, see:

http://www.cs.sunysb.edu/%7Ejgao/paper/layout-infocom08.pdf

and references therein.