Global Rigidity of Triangulations with Braces

Tibor Jordán, Shin-ichi Tanigawa

Published in:
Journal of Combinatorial Theory, Series B, Volume 136, 2019, Pages 249-288. DOI link


Cauchy proved that if the vertex-edge graphs of two convex polyhedra are isomorphic and corresponding faces are congruent then the two polyhedra are the same. This result implies that a convex polyhedron with triangular faces, as a bar-and-joint framework, is rigid.
A framework is said to be globally rigid if the bar lengths uniquely determine all pairwise distances between the joints. Global rigidity implies rigidity. It is well-known that every three-dimensional generic bar-and-joint realisation of the graph of a convex polyhedron with triangular faces (that we call a triangulation) is rigid. It is also known that if the number of vertices is at least five then such a realisation of a triangulation is never globally rigid.
In this paper we consider braced triangulations, obtained from triangulations by adding a set of extra bars (bracing edges) connecting pairs of non-adjacent vertices. We show that a braced triangulation is generically globally rigid in three-space if and only if it is 4-connected. The special case, when there is only one bracing edge, verifies a conjecture of Whiteley.
Our proof is based on a new result on the vertex splitting operation which may be of independent interest. We show that every graph which can be obtained from the complete graph on five vertices by non-trivial vertex splitting operations is generically globally rigid in three-space.

Bibtex entry:

AUTHOR = {Jord{\'a}n, Tibor and Tanigawa, Shin-ichi},
TITLE = {Global Rigidity of Triangulations with Braces},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2017},
NUMBER = {TR-2017-06}

Last modification: 26.5.2021. Please email your comments to Tamás Király!