Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let us assume that we are given a connected, undirected graph. Under the assumption that no three points are collinear, such a graph is uniquely realizable in the plane iff we can certify that it is generically globally rigid. A graph is generically globally rigid iff it is (i) generically redundantly rigid, and (ii) 3-connected (Laman, Hendrikson, Jackson and Jordan).

The graph below is 3-connected and generically rigid in the plane. However, it is not redundantly rigid (the removal of edge [4,3] permits nodes [1,2,5,6] to shear). Therefore, by definition it cannot be generically globally rigid. However, I cannot see any local or global degrees of freedom in this graph. A lack of generic rigidity would introduce an obvious flex, while a lack of 3-connectivity would introduce cut vertex pairs that form an axis of reflection. What degree of freedom does redundant rigidity constrain? Am I missing something? I apologise if this is painfully obvious.

alt text

share|improve this question
add comment

3 Answers 3

up vote 6 down vote accepted


         Flexing Graph

share|improve this answer
add comment

The graph is generically globally flexible in the plane (see Joe's example). But even for such a graph, there can be special (non-generic) drawings that are globally rigid. Yours is one such drawing. Violations in this direction can only occur when the drawing itself becomes infinitesimally flexible (ie. its rigidity matrix drops its rank).

share|improve this answer
add comment

As per your question of what degree of freedom redundant rigidity constrains, my understanding is this: if the graph is not redundantly rigid, then the removal of an edge (here 3-4), introduces an internal degree of freedom. As you move along that degree of freedom, the 3-4 distance is guaranteed (for some realizations), as I understand, to revert to its original value before the graph reverts to its original configuration, and therefore a second embedding of the original graph is produced.

share|improve this answer
    
Hi Yoav. Thank you very much for taking the time to explain this to me. I wish I could put a tick mark next to two answers! So, as I understand it, there is another type of global flexibility beyond a simple reflection. It seems as if a particular rigid framework can exist in a superposition. That is, there is no continuous movement that would take it from one valid configuration to the other (otherwise it would be locally flexible). –  Andrew Symington Jan 26 '12 at 11:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.