Stress-linked pairs of vertices and the generic stress matroid

Abstract

Given a graph $G$ and a mapping $p:V(G)\to {\mathbb{R}}^d$, we say that the pair $(G,p)$ is a ($d$-dimensional) realization of $G$. Two realizations $(G,p)$ and $(G,q)$ are equivalent if each of the point pairs corresponding to the edges of $G$ have the same distance under the embeddings $p$ and $q$. A pair of vertices $\{u,v\}$ is globally linked in $G$ in ${\mathbb{R}}^d$ if for every generic realization $(G,p)$ and every equivalent realization $(G,q)$, $(G+uv,p)$ and $(G+uv,q)$ are also equivalent. In this paper, we introduce and investigate the notion of $d$-stress-linked vertex pairs. Roughly speaking, a pair of vertices $\{u,v\}$ is $d$-stress-linked in $G$ if the edge $uv$ is generically stressed in $G+uv$ and for every generic $d$-dimensional realization $(G,p)$, every configuration $q$ that satisfies the equilibrium stresses of $(G,p)$ also satisfies the equilibrium stresses of $(G+uv,p)$. Among other results, we show that $d$-stress-linked vertex pairs are globally linked in ${\mathbb{R}}^d$, and we give a combinatorial characterization of $2$-stress-linked vertex pairs that matches the conjectural characterization of globally linked pairs in ${\mathbb{R}}^2$ due to Jackson et al. As a key tool, we introduce and study the ``algebraic dual'' of the $d$-dimensional generic rigidity matroid of a graph $G$, which we call the $d$-dimensional generic stress matroid of $G$. Our results about this matroid, which describes the global behavior of equilibrium stresses of generic realizations of $G$, may be of independent interest. We use our results to give positive answers to a conjecture of Jordán on minimally globally rigid graphs, a conjecture of Jordán and the author on globally linked vertex pairs, and to conjectures of Connelly and Grasegger et al. on rigidity properties of graphs with small separators.

improved presentation and some new/stronger results