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)



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.