Redundantly globally rigid braced triangulations
DOI:
https://doi.org/10.26493/1855-3974.2800.d12Keywords:
Triangulation, globally rigid graph, braced triangulation, rigidityAbstract
By mapping the vertices of a graph G to points in ℝ3, and its edges to the corresponding line segments, we obtain a three-dimensional realization of G. A realization of G is said to be globally rigid if its edge lengths uniquely determine the realization, up to congruence. The graph G is called globally rigid if every generic three-dimensional realization of G is globally rigid.
We consider global rigidity properties of braced triangulations, which are graphs obtained from maximal planar graphs by adding extra edges, called bracing edges. We show that for every even integer n ≥ 8 there exist braced triangulations with 3n − 4 edges which remain globally rigid if an arbitrary edge is deleted from the graph. The bound is best possible. This result gives an affirmative answer to a recent conjecture. We also discuss the connections between our results and a related more general conjecture, due to S. Tanigawa and the third author.
Downloads
Published
Issue
Section
License
Articles in this journal are published under Creative Commons Attribution 4.0 International License
https://creativecommons.org/licenses/by/4.0/