Does there exist a 3-connected, chordal graph which is not globally rigid? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T07:17:14Z http://mathoverflow.net/feeds/question/109151 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109151/does-there-exist-a-3-connected-chordal-graph-which-is-not-globally-rigid Does there exist a 3-connected, chordal graph which is not globally rigid? MrB 2012-10-08T14:23:07Z 2012-10-08T17:32:09Z <p>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?"</p> <p>It seems fairly intuitive to me that there does not, but my intuition about graphs has a fairly bad record...</p> <p>Thanks in advance.</p> http://mathoverflow.net/questions/109151/does-there-exist-a-3-connected-chordal-graph-which-is-not-globally-rigid/109157#109157 Answer by Steven Gortler for Does there exist a 3-connected, chordal graph which is not globally rigid? Steven Gortler 2012-10-08T15:21:31Z 2012-10-08T17:32:09Z <p>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 <a href="http://arxiv.org/abs/1205.3990" rel="nofollow">this paper</a> for some explicit statements. This idea generalizes to any dimension.</p> <p>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 <strong>any</strong> 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\$.)</p>