Periodic body-and-bar frameworks

ABSTRACT

Flexibility studies of macromolecules modeled as mechanical frameworks rely on computationally expensive, yet numerically imprecise simulations. Much faster approaches for degree-of-freedom counting and rigid component calculations are known for finite structures characterized by theorems of Maxwell-Laman type, but such results are exceedingly rare and difficult to obtain. The situation is even more complex for infinite, periodic structures such as those appearing in the study of crystalline materials. Here, an adequate rigidity theoretical formulation has been proposed only recently, opening the way to a combinatorial treatment.

Abstractions of crystalline materials known as periodic body-and-bar frameworks are made of rigid bodies connected by fixed-length bars and subject to the action of a group of translations. In this paper, we give a Maxwell-Laman characterization for generic minimally rigid periodic body-and-bar frameworks in terms of their quotient graphs. As a consequence we obtain efficient polynomial time algorithms for their recognition based on matroid partition and pebble games.

References

1. C. S. Borcea and I. Streinu. Periodic frameworks and flexibility. Proceedings of the Royal Society A 8, 466(2121):2633--2649, September 2010.
2. C. S. Borcea and I. Streinu. Minimally rigid periodic graphs. Bulletin of the London Mathematical Society, 2011.
3. C. S. Borcea, I. Streinu, and S. Tanigawa. Periodic body-and-bar frameworks. arXiv:1110.4660, 2011.
4. J. H. Conway and N. J. A. Sloane. Sphere packings, lattices and groups, volume 290 of Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, New York, 3rd edition, 1999.
5. O. Delgado-Friedrichs. Equilibrium placement of periodic graphs and convexity of plane tilings. Discrete and Computational Geometry, 33:67--81, 2005.
6. V. S. Deshpande, M. F. Ashby, and N. A. Fleck. Foam topology: bending versus stretching dominated architectures. Acta Materialia, 49(6):1035--1040, 2001.
7. G. Dolino. The α-inc-β transitions in quartz: a century of research on displacive phase transitions. Phase Transitions, 21:59--72, 1990.
8. A. Donev and S. Torquato. Energy-efficient actuation in infinite lattice structures. Journal of the Mechanics and Physics of Solids, 51:1459--1475, 2003.
9. M. T. Dove. Theory of displacive phase transitions in minerals. American Mineralogist, 82:213--244, 1997.
10. J. Edmonds. Minimum partition of a matroid into independent sets. J. Res. Nat. Bur. Standards Sect. B, 69B:67--72, 1965.
11. N. Fox, F. Jagodzinski, Y. Li, and I. Streinu. KINARI-Web: A server for protein rigidity analysis. Nucleic Acids Research, 39(Web Server Issue), 2011.
12. A. L. Goodwin. Rigid unit modes and intrinsic flexibility of linearly bridged framework structures. Physical Review B, 74:132302--132312, 2006.
13. S. Guest and J. W. Hutchinson. On the determinacy of repetitive structures. Journal of the Mechanics and Physics of Solids, 51:383--391, 2003.
14. R. Haas, A. Lee, I. Streinu, and L. Theran. Characterizing sparse graphs by map decompositions. Journal of Combinatorial Mathematics and Combinatorial Computing, 62:3--11, 2007.
15. D. Hilbert and S. Cohn-Vossen. Geometry and the Imagination. Chelsea Publishing Company, New York, 1962.
16. R. G. Hutchinson and N. A. Fleck. The structural performance of the periodic truss. Journal of the Mechanics and Physics of Solids, 54:765--782, 2006.
17. B. Jackson and T. Jordán. The generic rank of body-bar-and-hinge frameworks. European Journal of Combinatorics, 31(2):574--588, 2009.
18. V. Kapko, M. M. J. Treacy, M. F. Thorpe, and S. Guest. On the collapse of locally isostatic networks. Proceedings of the Royal Society A, 465:3517--3530, 2009.
19. N. Katoh and S. Tanigawa. A proof of the molecular conjecture. Discrete and Computational Geometry, 45(4):647--700, 2011. Prelim. version in Proc. Symp. Comp. Geometry (SoCG), 2008.
20. M. Kotani and T. Sunada. Standard realizations of crystal lattices via harmonic maps. Transactions of the American Mathematical Society, 353:1--20, 2001.
21. G. Laman. On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics, 4:331--340, 1970.
22. A. Lee and I. Streinu. Pebble game algorithms and sparse graphs. Discrete Mathematics, 308(8):1425--1437, April 2008.
23. J. Lima-de Faria, editor. Historical Atlas of Crystallography. Kluwer, IUC, 1990.
24. J. Malestein and L. Theran. Generic combinatorial rigidity of periodic frameworks. arxiv.1008.1837, 2010.
25. J. C. Maxwell. On the calculation of the equilibrium and stiffness of frames. Philosophical Magazine, 27:294--299, 1864.
26. H. D. Megaw. Crystal structures: a working approach. W.B.Saunders Co., Philadelphia, 1973.
27. M. O'Keeffe, M. Eddaoudi, H. Li, T. Reineke, and O. M. Yaghi. Frameworks for extended solids: geometrical design principles. Journal of Solid State Chemistry, 152:3--20, 2000.
28. J. G. Oxley. Matroid theory. The Clarendon Press, Oxford University Press, New York, 1992.
29. S. C. Power. Crystal frameworks, symmetry and affinely periodic flexes. arXiv:1103.1914, 2011.
30. J. S. Pym and H. Perfect. Submodular functions and independence structures. Journal of Mathematical Analysis and Applications, 30:1--31, 1970.
31. E. Ross. Geometric and combinatorial rigidity of periodic frameworks as graphs on the torus. PhD thesis, York University, Ontario, Canada, Toronto, May 2011.
32. E. Ross, B. Schulze, and W. Whiteley. Finite motions from periodic frameworks with added symmetry. International Journal Solids and Structures, 48:1711--1729, 2011.
33. S. Tanigawa. Generic rigidity matroids with Dilworth truncations. arXiv:1010.5699, 2010.
34. T.-S. Tay. Rigidity of multigraphs I: linking rigid bodies in n-space. Journal of Combinatorial Theory, Series B, 26:95--112, 1984.
35. T.-S. Tay. Linking (n-2)-dimensional panels in n-space II: $(n-2, 2)-frameworks and body and hinge structures. Graphs and Combinatorics, 5:245--273, 1989.
36. T.-S. Tay. Linking (n-2)-dimensional panels in n-space I:(k-1, k)-graphs and (k-1, k)-frames. Graphs and Combinatorics, 7(3):289--304, 1991.
37. M. F. Thorpe, M. V. Chubynsky, B. M. Hespenheide, S. Menor, D. J. Jacobs, L. A. Kuhn, M. I. Zavodszky, M. Lei, A. J. Rader, and W. Whiteley. Flexibility in Biomolecules, chapter 6, pages 97--112. Current Topics in Physics. Imperial College Press, London, 2005. R.A. Barrio and K.K. Kaski, eds.
38. H. Weyl. Symmetry. Princeton University Press, 1952.
39. W. Whiteley. The union of matroids and the rigidity of frameworks. SIAM Journal Discrete Mathematics, 1(2):237--255, May 1988.

Index Terms

• Computing methodologies

  • Computer graphics

    • Shape modeling

• Theory of computation

  • Randomness, geometry and discrete structures