|
A graph $G = (V,E)$ is globally rigid in $\R^d$ if for any generic placement $p : V \rightarrow \R^d$ of the vertices, the edge lengths $\norm{p(u) - p(v)}, uv \in E$ uniquely determine $p$, up to congruence.
In this paper we consider minimally globally rigid graphs, in which the deletion of an arbitrary edge destroys
global rigidity. We prove that if $G=(V,E)$ is minimally globally rigid in $\R^d$ on at least $d+2$ vertices, then $|E|\leq (d+1)|V|-\binom{d+2}{2}$. This implies that the minimum degree of $G$ is at most $2d+1$. We also show that the only graph in which the upper bound on the number of edges is attained is the complete graph $K_{d+2}$. It follows that every minimally globally rigid graph in $\R^d$ on at least $d+3$ vertices is flexible in $\R^{d+1}$.
As a counterpart to our main result on the sparsity of minimally globally rigid graphs, we show that in two dimensions, dense graphs always contain non-trivial globally rigid subgraphs.
More precisely, if some graph $G=(V,E)$ satisfies $|E|\geq 5|V|$, then $G$ contains a globally rigid subgraph on at least seven vertices in $\R^2$. If the well-known ``sufficient connectivity conjecture'' is true, then this result also extends to higher dimensions.
Finally, we discuss a conjectured strengthening of our main result, which states that if a pair of vertices $\{u,v\}$ is linked in $G$ in $\RR^{d+1}$, then $\{u,v\}$ is globally linked in $G$ in $\RR^d$. We prove this conjecture in the $d=1,2$ cases, along with a variety of related results.
Bibtex entry:
| AUTHOR | = | {Garamvölgyi, D{\'a}niel and Jord{\'a}n, Tibor}, |
| TITLE | = | {Minimally globally rigid graphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2022}, |
| NUMBER | = | {TR-2022-04} |