Home > Research > Publications & Outputs > Inductive constructions for combinatorial local...
View graph of relations

Inductive constructions for combinatorial local and global rigidity

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNChapter (peer-reviewed)peer-review

Publication date20/07/2018
Host publicationHandbook of Geometric Constraint Systems Principles
EditorsMeera Sitharam, Audrey St. John, Jessica Sidman
PublisherCRC Press
Number of pages22
ISBN (Electronic)9781315121116
ISBN (Print)9781498738910
<mark>Original language</mark>English

Publication series

NameDiscrete Mathematics and Its Applications
PublisherCRC Press


Determining the rigidity, or global rigidity, of a given framework is NP-hard. This chapter considers a variety of local operations on graphs and when they are known to preserve the rigidity or global rigidity of frameworks. However, the situation improves for generic frameworks where one can linearize the problem and characterize generic rigidity via the rank of the rigidity matrix. A key topic in rigidity theory, perhaps the fundamental topic, is to characterize generic rigidity, and generic global rigidity, in purely combinatorial terms. For body-bar frameworks, rigidity can be elegantly characterized via tree packing in arbitrary dimension. Known characterizations of incidental rigidity are limited to very small groups but make significant use of inductive constructions. It is helpful to have inductive methods to generate families of globally rigid direction-length graphs, and this provides a tool to verify the global rigidity of certain frameworks.