TR-2018-01

Sufficient conditions for the global rigidity of periodic graphs

Viktória Kaszanitzky, Csaba Király, Bernd Schulze



Abstract

Tanigawa (2016) showed that vertex-redundant rigidity of a graph implies its global rigidity in arbitrary dimension. We extend this result to periodic graphs under fixed lattice representations. A periodic graph is vertex-redundantly rigid if the deletion of a single vertex orbit under the periodicity results in a periodically rigid graph. Our proof is similar to the one of Tanigawa, but there are some added difficulties. First, it is not known whether periodic global rigidity is a generic property. This issue is resolved via a slight modification of a recent result of Kaszanitzy, Schulze and Tanigawa (2016). Secondly, while the rigidity of finite graphs in $\mathbb{R}^d$ on at most $d$ vertices obviously implies their global rigidity, it is non-trivial to prove a similar result for periodic graphs. This is accomplished by extending a result of Bezdek and Connelly (2002) on the existence of a continuous movement between two equivalent $d$-dimensional realisations of a single graph in $\mathbb{R}^{2d}$ to periodic frameworks.
 
As an application of our result, we give a necessary and sufficient condition for the global rigidity of generic periodic body-bar frameworks in arbitrary dimension. This provides a periodic counterpart to a result of Connelly, Jordán and Whiteley (2013) regarding the global rigidity of generic finite body-bar frameworks.


Bibtex entry:

@techreport{egres-18-01,
AUTHOR = {Kaszanitzky, Vikt{\'o}ria and Kir{\'a}ly, Csaba and Schulze, Bernd},
TITLE = {Sufficient conditions for the global rigidity of periodic graphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2018},
NUMBER = {TR-2018-01}
}


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