TR-2020-14

Global rigidity of (quasi)-injective frameworks on the line

Dániel Garamvölgyi



Abstract

A realization of a graph $G$ is a pair $(G,p)$ where $p$ maps the vertices of $G$ into Euclidean space $\R^d$. The realization is injective if $p$ is injective and quasi-injective if for each edge of $G$, $p$ maps the endpoints of the edge to different points in space. The realization is globally rigid if any realization $(G,q)$ in $\R^d$ with the same edge lengths is congruent to $(G,p)$.
 
In this paper we characterize graphs that have an injective (quasi-injective, respectively) non-globally rigid realization in $\R^1$, and we show that the problem of recognizing these graphs is NP-complete in both the injective and the quasi-injective cases. Our characterizations are based on the notion of NAC-colorings, which have been used previously to investigate similar problems in the plane. We also give an overview of related results and open problems in rigidity theory.


Bibtex entry:

@techreport{egres-20-14,
AUTHOR = {Garamvölgyi, D{\'a}niel},
TITLE = {Global rigidity of (quasi)-injective frameworks on the line},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2020},
NUMBER = {TR-2020-14}
}


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