Abstract
We present a survey of results concerning the use of inductive constructions to study the rigidity of frameworks. By inductive constructions we mean simple graph moves which can be shown to preserve the rigidity of the corresponding framework. We describe a number of cases in which characterisations of rigidity were proved by inductive constructions. That is, by identifying recursive operations that preserved rigidity and proving that these operations were sufficient to generate all such frameworks. We also outline the use of inductive constructions in some recent areas of particularly active interest, namely symmetric and periodic frameworks, frameworks on surfaces, and body-bar frameworks. As the survey progresses we describe the key open problems related to inductions.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Asimow, L., Roth, B.: The rigidity of graphs. Trans. Am. Math. Soc. 245, 279–289 (1978)
Berg, A.R., Jordán, T.: A proof of Connelly’s conjecture on 3-connected circuits of the rigidity matroid. J. Combin. Theory B 88(1), 77–97 (2003)
Borcea, C., Streinu, I.: The number of embeddings of minimally rigid graphs. Discret. Comput. Geom. 31(2), 287–303 (2004)
Borcea, C., Streinu, I.: Minimally rigid periodic graphs. Bull. Lond. Math. Soc. 43, 1093–1103 (2010)
Borcea, C.S., Streinu, I.: Periodic frameworks and flexibility. Proc. R. Soc. A 466(2121), 2633–2649 (2010)
Borcea, C.S., Streinu, I., Tanigawa, S.-I.: Periodic body-and-bar frameworks. In: Proceedings of the 2012 Symposium on Computational Geometry, SoCG’12, Chapel Hill, pp. 347–356. ACM, New York (2012)
Cheung, M., Whiteley, W.: Transfer of global rigidity results among dimensions: graph powers and coning (2008, preprint)
Connelly, R.: Generic global rigidity. Discret. Comput. Geom. 33(4), 549–563 (2005)
Connelly, R., Jordán, T., Whiteley, W.: Generic global rigidity of body-bar frameworks J. Combin. Theory Ser. B 103(6), 689–705 (2013)
Fekete, Z., Szegő, L.: A note on [k, l]-sparse graphs. In: Graph Theory, pp. 169–177. Birkhäuser, Cambridge (2006)
Finbow, W., Whiteley, W.: Isostatic block and hole frameworks. SIAM J. Discret. Math. 27(2), 991–1020 (2013)
Frank, A., Szegő, L.: Constructive characterizations for packing and covering with trees. Discret. Appl. Math. 131(2), 347–371 (2003)
Graver, J., Servatius, B., Servatius, H.: Combinatorial Rigidity. Volume 2 of Graduate Studies in Mathematics. American Mathematical Society, Providence (1993)
Haas, R., Orden, D., Rote, G., Santos, F., Servatius, B., Servatius, H., Souvaine, D., Streinu, I., Whiteley, W.: Planar minimally rigid graphs and pseudo-triangulations. Comput. Geom. Theory Appl. 31(1–2), 63–100 (2005)
Hendrickson, B.: Conditions for unique graph realizations. SIAM J. Comput. 21(1), 65–84 (1992)
Henneberg, L.: Die Graphische der Starren Systeme. B.G. Teubner, Leipzig (1911)
Jackson, B., Jordán, T.: Connected rigidity matroids and unique realizations of graphs. J. Combin. Theory B 94(1), 1–29 (2005)
Jackson, B., Jordán, T.: Graph Theoretic Techniques in the Analysis of Uniquely Localizable Sensor Networks. In: Mao,G., Fidanm, B. (eds.), Localization Algorithms and Strategies for Wireless Sensor Networks, pp. 145–173. IGI Global (2009)
Jackson, B., Jordán, T.: Globally rigid circuits of the direction-length rigidity matroid. J. Combin. Theory B 100(1), 1–22 (2010)
Jackson, B., Owen, J.: The number of equivalent realisations of a rigid graph. arXiv:1204.1228 (2012, preprint)
Jackson, B., Jordán, T., Szabadka, Z.: Globally linked pairs of vertices in equivalent realizations of graphs. Discret. Comput. Geom. 35(3), 493–512 (2006)
Jordán, T., Szabadka, Z.: Operations preserving the global rigidity of graphs and frameworks in the plane. Comput. Geom. 42(6–7), 511–521 (2009)
Jordán, T., Kaszanitsky, V., Tanigawa, S.: Gain-sparsity and symmetry-forced rigidity in the plane EGRES technical report TR-2012-17 (2012)
Katoh, N., Tanigawa, S.: A proof of the molecular conjecture. Discret. Comput. Geom. 45(4), 647–700 (2011)
Laman, G.: On graphs and rigidity of plane skeletal structures. J. Eng. Math. 4:331–340 (1970)
Lee, A., Streinu, I.: Pebble game algorithms and sparse graphs. Discret. Math. 308(8), 1425–1437 (2008)
Malestein, J., Theran, L.: Generic rigidity of frameworks with orientation-preserving crystallographic symmetry. arXiv:1108.2518 (2011)
Malestein, J., Theran, L.: Frameworks with forced symmetry i: reflections and rotations. arxXiv:1304.0398 (2012, preprint)
Malestein, J., Theran, L.: Generic combinatorial rigidity of periodic frameworks. Adv. Math. 233, 291–331 (2013)
Maxwell, J.C.: On the claculation of the equilibrium and stiffness of frames. Philos. Mag. 27, 294–299 (1864)
Nash-Williams, C.S.J.: Edge-disjoint spanning trees of finite graphs. J. Lond. Math. Soc. 2(36), 445–450 (1961)
Nixon, A.: A constructive characterisation of circuits in the simple (2, 2)-sparsity matroid. arXiv:1202.3294v2 (2012, preprint)
Nixon, A., Owen, J.: An inductive construction of (2, 1)-tight graphs. arXiv:1103.2967v2 (2011, preprint)
Nixon, A., Ross, E.: Periodic rigidity on a variable torus using inductive constructions. arXiv:1204.1349 (2012, preprint)
Nixon, A., Owen, J., Power, S.: A laman theorem for frameworks on surfaces of revolution. arXiv:1210.7073v2 (2012, preprint)
Nixon, A., Owen, J.C., Power, S.C.: Rigidity of frameworks supported on surfaces. SIAM J. Discret. Math. 26(4), 1733–1757 (2012)
Pilaud, V., Santos, F.: Multitriangulations as complexes of star polygons. Discret. Comput. Geom. 41(2), 284–317 (2009)
Recent Progress in Rigidity Theory 08w2137, Banff International Research Station. http://www.birs.ca/workshops/2008/08w2137/report08w2137.pdf. Accessed 11–13 July 2008
Recski, A.: Matroid Theory and its Applications in Electric Network Theory and in Statics. Volume 6 of Algorithms and Combinatorics. Springer, Berlin (1989)
Rigidity of periodic and symmetric structures in nature and engineering, The Kavli Royal Society International Centre. http://royalsociety.org/events/Rigidity-of-periodic-and-symmetric-structures/. Accessed 23–24 Feb 2012
Ross, E.: The geometric and combinatorial rigidity of periodic graphs. PhD thesis, York University (2011). http://www.math.yorku.ca/~ejross/RossThesis.pdf
Ross, E.: The rigidity of periodic body-bar frameworks on the three-dimensional fixed torus. Phil. Trans. R. Soc. A, 372 (2014)
Rote, G., Santos, F., Streinu, I.: Pseudo-triangulations – a survey. In: Goodman, J.E., Pach, J., Pollack, R. (eds.), Surveys on Discrete and Computational Geometry: Twenty Years Later. Volume 453 of Contemporary Mathematics, pp. 343–410. American Mathematical Society, Providence (2008)
Schulze, B.: Symmetric Laman theorems for the groups \(\mathcal{C}_{2}\) and \(\mathcal{C}_{s}\). Electron. J. Combin. 17(1), 1–61 (2010)
Schulze, B.: Symmetric versions of Laman’s theorem. Discret. Comput. Geom. 44(4), 946–974 (2010)
Servatius, B., Servatius, H.: On the 2-sum in rigidity matroids. Eur. J. Combin. 32(6), 931–936 (2011)
Servatius, B., Whiteley, W.: Constraining plane configurations in computer-aided design: combinatorics of directions and lengths. SIAM J. Discret. Math. 12(1), 136–153 (1999, electronic)
Streinu, I.: Parallel-redrawing mechanisms, pseudo-triangulations and kinetic planar graphs. In: Graph Drawing. Volume 3843 of Lecture Notes in Computer Science, pp. 421–433. Springer, Berlin (2006)
Tay, T.-S.: Rigidity of multigraphs I: linking rigid bodies in n-space. J. Combin. Theory B 26, 95–112 (1984)
Tay, T.-S.: Henneberg’s method for bar and body frameworks. Struct. Topol. 17, 53–58 (1991)
Tay, T.-S.: On the generic rigidity of bar-frameworks. Adv. Appl. Math. 23(1), 14–28 (1999)
Tay, T.-S., Whiteley, W.: Generating isostatic frameworks. Struct. Topol. 11, 21–69 (1985). Dual French-English text
Whiteley, W.: Vertex splitting in isostatic frameworks. Struct. Topol. 16, 23–30 (1990). Dual French-English text
Whiteley, W.: Some matroids from discrete applied geometry. In: Matroid theory (Seattle, 1995). Volume 197 of Contemporary Mathematics, pp. 171–311. American Mathematical Society, Providence (1996)
Whiteley, W.: Rigidity and scene analysis. In: Handbook of Discrete and Computational Geometry. CRC Press Series on Discrete Mathematics and its Applications, pp. 893–916. CRC, Boca Raton (1997)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer Science+Business Media New York
About this chapter
Cite this chapter
Nixon, A., Ross, E. (2014). One Brick at a Time: A Survey of Inductive Constructions in Rigidity Theory. In: Connelly, R., Ivić Weiss, A., Whiteley, W. (eds) Rigidity and Symmetry. Fields Institute Communications, vol 70. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-0781-6_15
Download citation
DOI: https://doi.org/10.1007/978-1-4939-0781-6_15
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4939-0780-9
Online ISBN: 978-1-4939-0781-6
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)