By mapping the vertices of a graph $G$ to points in $\mathbb{R}^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\geq 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.
Bibtex entry:
AUTHOR | = | {Chen, Qianfan and Jajodia, Siddhant and Jord{\'a}n, Tibor and Perkins, Kate}, |
TITLE | = | {Redundantly globally rigid braced triangulations}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2021}, |
NUMBER | = | {TR-2021-12} |