Globally linked pairs of vertices in generic frameworks

arXiv2307.04451MaRDI QIDQ6443151FDOQ6443151

Authors: Tibor Jordán, Soma Villányi 

Publication date: 10 July 2023

Abstract: A $d$-dimensional framework is a pair $(G,p)$, where $G=(V,E)$ is a graph and $p$ is a map from $V$ to $mathbb{R}^d$. The length of an edge $xyinE$ in $(G,p)$ is the distance between $p(x)$ and $p(y)$. A vertex pair $u,v$ of $G$ is said to be globally linked in $(G,p)$ if the distance between $p(u)$ and $p(v)$ is equal to the distance between $q(u)$ and $q(v)$ for every $d$-dimensional framework $(G,q)$ in which the corresponding edge lengths are the same as in $(G,p)$. We call $(G,p)$ globally rigid in $mathbb{R}^d$ when each vertex pair of $G$ is globally linked in $(G,p)$. A pair $u,v$ of vertices of $G$ is said to be weakly globally linked in $G$ in $mathbb{R}^d$ if there exists a generic framework $(G,p)$ in which $u,v$ is globally linked. In this paper we first give a sufficient condition for the weak global linkedness of a vertex pair of a $(d+1)$-connected graph $G$ in $mathbb{R}^d$ and then show that for $d=2$ it is also necessary. We use this result to obtain a complete characterization of weakly globally linked pairs in graphs in $mathbb{R}^2$, which gives rise to an algorithm for testing weak global linkedness in the plane in $O(|V{|}^2)$ time. Our methods lead to a new short proof for the characterization of globally rigid graphs in $mathbb{R}^2$, and further results on weakly globally linked pairs and globally rigid graphs in the plane and in higher dimensions.

This page was built for publication: Globally linked pairs of vertices in generic frameworks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6443151)