A Taxonomy on Rigidity of Graphs

Objective: In the material world, objects like railway tracks, bridges, roofs etc., are constructed by collections of nonelastic rigid rods, beams, etc.. A structure is said to be rigid if there is no continuous motion of the structure that changes its shape without changing the shapes of its components like rods or beams. In this survey work, we accumulate the fundamental concepts on graph rigidity. Methods and Analysis: We give the analytical definition of rigid graphs using the idea of rigid motions. The Laman’s theorem and Hendrickson’s algorithm are presented as methods for testing graph rigidity in the plane. The construction of the rigid graphs is also analyzed using the Henneberg’s operations. We describe how in distributed environments the rigidity of graphs can be checked using the vertex ordering in the graph. For frameworks lying in the higher dimensional spaces rigidity testing method is presented in form of a theorem. Novelty and Improvements: The results of this review works may help the readers to better understand the graph rigidity theory from different perspectives. This study founds a positive association between the analytical and combinatorial concepts of graph rigidity investigated so far.