2
$\begingroup$

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 http://www.freeimagehosting.net/newuploads/2bl75.png

$\endgroup$
1
  • 2
    $\begingroup$ The link doesn't work: it immediately redirects to www.freeimagehosting.net, so without all the specification $\endgroup$
    – Vincent
    Jul 10, 2017 at 19:27

3 Answers 3

8
$\begingroup$


         Flexing Graph
         Image created using Cinderella.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$ Jan 26, 2012 at 11:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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