Final published version
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter (peer-reviewed) › peer-review
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter (peer-reviewed) › peer-review
}
TY - CHAP
T1 - Inductive constructions for combinatorial local and global rigidity
AU - Nixon, Anthony Keith
AU - Ross, Elissa
PY - 2018/7/20
Y1 - 2018/7/20
N2 - 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.
AB - 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.
U2 - 10.1201/9781315121116
DO - 10.1201/9781315121116
M3 - Chapter (peer-reviewed)
SN - 9781498738910
T3 - Discrete Mathematics and Its Applications
BT - Handbook of Geometric Constraint Systems Principles
A2 - Sitharam, Meera
A2 - St. John, Audrey
A2 - Sidman, Jessica
PB - CRC Press
ER -