TR-2018-17

Global Rigidity of Unit Ball Graphs

Dániel Garamvölgyi, Tibor Jordán



Abstract

A $d$-dimensional bar-and-joint framework $(G,p)$, where $G$ is a graph and $p$ maps the vertices of $G$ to points in $\R^d$, is said to be globally rigid if every $d$-dimensional framework $(G,q)$ with the same graph and same edge lengths is congruent to $(G,p)$. Global rigidity of frameworks and graphs is a well-studied area of rigidity theory with a number of applications, including the localization problem of sensor networks.
 
Motivated by this application we consider the new notion of unit ball global rigidity, which can be defined similarly, except that $(G,p)$ as well as $(G,q)$ are required to be unit ball frameworks in the above definition. In a unit ball framework two vertices are adjacent if and only if their distance is less than a fixed constant (which corresponds to the sensing radius in a sensor network).
 
In this paper we initiate a theoretical analysis of this version of global rigidity and prove several structural results. Among others we identify families of frameworks (and corresponding graphs $G$) in $\R^d$, for all $d\geq 1$, which are unit ball globally rigid without being globally rigid in the usual sense. These families contain minimally rigid graphs, too, which have less edges than any of the globally rigid graphs on the same number of vertices.


Bibtex entry:

@techreport{egres-18-17,
AUTHOR = {Garamvölgyi, D{\'a}niel and Jord{\'a}n, Tibor},
TITLE = {Global Rigidity of Unit Ball Graphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2018},
NUMBER = {TR-2018-17}
}


Last modification: 29.12.2020. Please email your comments to Tamás Király!