Total views : 71

A Taxonomy on Rigidity of Graphs


  • Department of Mathematics, Jadavpur University, Kolkata - 700032, West Bengal, India
  • Department of Computer Science and Engineering, Birla Institute of Technology, Mesra, Kolkata - 700107, West Bengal, India


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.


Graph Realization, Localizability Testing, Network Localization, Rigidity of Graphs

Full Text:

 |  (PDF views: 65)


  • Apostol TM. Mathematical Analysis. 2nd ed. Addison Wesley publisher; 1974.
  • Biedl T, Lubiw A, Spriggs M. Cauchys theorem and edge lengths of convex polyhedra. Algorithms and Data Structures.2007 Aug; 4619:398–409.
  • Izmestiev I. Infinitesimal rigidity of frameworks and surfaces.University spring; 2009. p. 1–79.
  • Crapo H. Structural rigidity. Structural Topologl. 1979; 1:26–45.
  • Wallace A. Algebraic approximation of curves. Canad Journal of Mathathematics. 1958; 10:242–78. Crossref
  • Hermary ME. Rigidity of graphs a thesis submitted in partial fulfilment of the requirement for the degree of Master of Science; 1986.
  • Roth B, Whiteley W. Tensegrity framework. Transactions of American Mathematical Society. 1981; 265(2):1–28.Crossref
  • Jackson B, Jordan T. Connected rigidity matroids and unique realizations of graphs. Journal of Combinatorial Theory Series B. 2005; 94(1):1–29. Crossref
  • Krishanan NSG. University Algebra. 3rd ed. New Age International Limited Publisher; 2004.
  • Herstain IN. Topics in algebra. 2nd ed. John Wiley and Sons Publisher; 1975. p. 1–401.
  • Connelly R. Generic global rigidity. Discrete and Computational Geometry; 2005. p. 549–63. Crossref
  • Hendrickson B. Conditions for unique graph realizations.SIAM Journal on Computing. 1992; 21(1):65–84. Crossref
  • Laman G. On graphs and rigidity of plane skeletal structures.Journal of Engineering Mathematics. 1970 Dec; 4(4):331–40. Crossref
  • Connelly R. On generic global rigidity, applied geometry and discrete mathematics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science; 1991. p.147–55.
  • Connelly R. Jordan T, Whiteley W. Generic global rigidity of baby-bar framework. Journal of Combinatorial Theory.2009 Dec. p. 689–705.
  • Oxley JG. Matroid theory. 1st ed. Oxford University Press; 1992.
  • Biswas P, Chuan TK, Yinyu Y. A distributed SDP approach for large-scale noisy anchor-free graph realization with applications to molecular conformation. SIAM Journal on Scientific Computing archive. 2008 Mar; 30(3):1251–77.
  • Doherty L, Pister KSJ, Ghaoui LE. Convex position estimation in wireless sensor net-works. 20th Annual Joint Conference of the IEEE Computer and Communications Societies Proceedings; 2001. p. 1655–63.
  • Mukhopadhyaya S, Sau B. Rigidity of graphs. CSI Communications.2014; 38(2):17–8.
  • Sau B, Mukhopadhyaya K. Localizability of wireless sensor networks: Beyond wheel ex-tension. Stabilization Safety and Security of Distributed Systems 15th International Symposium SSS 2013; 2013 Nov. p. 326–40.
  • Goldenberg D, Bihler KP, Cao M, Fang J, Anderson DO, Morse AS, Yang YR. Localization in sparse networks using sweeps. Proceedings of the 12th annual international conference on Mobile computing and networking; 2006. p.110–21.
  • Asimow L, Roth B. The rigidity of graphs. Transactions of American Mathematical Society. 1978 Nov; 245(4):279–89.Crossref
  • Roth B. Rigid and exible frameworks. The American Mathematical Monthly. 1981 Jan; 88(1):6–21. Crossref
  • Saber RO, Murray RM. Graph rigidity and distributed formation stabilization of multi-vehicle systems. Proceedings of the 41st IEEE Conference on Decision and Control; 2002. p. 2965–71.
  • Sau B, Mukhopadhyaya K. Length-based anchor-free localization in a fully covered sensor network. In Proceedings of the First international conference on COMmunication Systems And NETworks, COMSNETS’09; 2009. p. 1–10.PMid:19537157
  • Sljoka A. Algorithms in rigidity theory with applications to protein flexibility and me-chanical linkages. York University; 2012 Aug.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.