Sparsity, stress-independence and globally linked pairs in graph rigidity theory

Source abstract

Abstract A graph is ${\mathcal {R}}_{d}$-independent (resp. ${\mathcal {R}}_{d}$-connected) if its $d$-dimensional generic rigidity matroid is free (resp. connected). A result of Maxwell implies that every ${\mathcal {R}}_{d}$-independent graph satisfies the sparsity condition $|E(H)|\leq d|V(H)|-\binom{d+1}{2}$ for all subgraphs $H$ with at least $d+1$ vertices. Several other families of graphs $G$ arising in rigidity theory, such as minimally globally $d$-rigid graphs, are known to satisfy the bound $|E(G)|\leq (d+1)|V(G)|-\binom {d+2}{2}$. We unify and extend these sparsity results by considering the family of $d$-stress-independent graphs, which includes many of these families, and showing that every $d$-stress-independent graph is ${\mathcal {R}}_{d+1}$-independent. We also give a sharp upper bound on the number of edges in $2$-stress-independent graphs on at least eight vertices. A key ingredient in our proofs is the concept of $d$-stress-linked pairs of vertices. We extend a result of Tanigawa on globally $d$-rigid graphs by showing that if a pair of vertices is vertex-redundantly $d$-linked in $G$, or $(d+1)$-linked in $G$, then the vertex pair is $d$-stress-linked in $G$. We also show that every minimally ${\mathcal {R}}_{d}$-connected graph $G$ is ${\mathcal {R}}_{d+1}$-independent and that the only subgraphs of $G$ that can satisfy Maxwell’s criterion for ${\mathcal {R}}_{d+1}$-independence with equality are copies of $K_{d+2}$.