Sparsity, Stress-Independence and Globally Linked Pairs in Graph Rigidity Theory

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 from 1867 implies that every ${\mathcal{R}}_d$-independent graph satisfies the sparsity condition $|E(H)|\le d|V(H)|-\left(\genfrac{}{}{0ex}{}{d+1}{2}\right)$ for all subgraphs $H$ with at least $d+1$ vertices. Several other families of graphs $G$ arising naturally in rigidity theory, such as minimally globally $d$-rigid graphs, are known to satisfy the bound $|E(G)|\le (d+1)|V(G)|-\left(\genfrac{}{}{0ex}{}{d+2}{2}\right)$. We unify and extend these results by considering the family of $d$-stress-independent graphs which includes many of these families. We show that every $d$-stress-independent graph is ${\mathcal{R}}_{d+1}$-independent. A key ingredient in our proofs is the concept of $d$-stress-linked pairs of vertices. We derive a new sufficient condition for $d$-stress linkedness and use it to obtain a similar condition for a pair of vertices of a graph to be globally $d$-linked. This result strengthens a result of Tanigawa on globally $d$-rigid graphs. 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}$. Our results give affirmative answers to two conjectures in graph rigidity theory.