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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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$.)

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .