Sparsity, Stress-Independence and Globally Linked Pairs in Graph Rigidity Theory
Preprint
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)|\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 naturally 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 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.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Minimally Rigid Tensegrity FrameworksDiscrete & Computational Geometry, 2025
- Ear‐decompositions, minimally connected matroids and rigid graphsJournal of Graph Theory, 2023
- Minimally globally rigid graphsEuropean Journal of Combinatorics, 2022
- Flexible circuits in the d‐dimensional rigidity matroidJournal of Graph Theory, 2021
- Sufficient conditions for the global rigidity of graphsJournal of Combinatorial Theory, Series B, 2015
- The Dress conjectures on rank in the 3-dimensional rigidity matroidAdvances in Applied Mathematics, 2005
- Connected rigidity matroids and unique realizations of graphsJournal of Combinatorial Theory, Series B, 2005
- Independence and port oracles for matroids, with an application to computational learning theoryCombinatorica, 1996
- k-connectivity and decomposition of graphs into forestsDiscrete Applied Mathematics, 1994
- Conditions for Unique Graph RealizationsSIAM Journal on Computing, 1992