1
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

5
$\begingroup$

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

$\endgroup$
0

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.