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

The question is in the title! I know that a globally rigid graph is 3-connected and redundantly rigid, so my question could be rephrased as: "does there exist a graph which is 3-connected and chordal but not redundantly rigid?"

It seems fairly intuitive to me that there does not, but my intuition about graphs has a fairly bad record...

Thanks in advance.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

Every such graph is generically globally rigid in $E^2$. A 3-connected chordal graph can be built by starting with a triangle and then sequentially attaching new vertices to at least 3 previous ones. See this paper for some explicit statements. This idea generalizes to any dimension.

In fact, any generic (or even general position) framework for such a graph will be universally rigid in $E^2$, ie. it has no equivalent and non-congruent frameworks in any dimension. Such a graph is called generically universally rigid in $E^2$. (Note that you need to be a bit careful with universal rigidity as there are graphs that have some generic frameworks that are universally rigid in $E^2$, and other generic frameworks that are not universally rigid in $E^2$.)

share|improve this answer
    
thanks, much appreciated. –  MrB Oct 8 '12 at 15:36

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.