AnAlgorithmforTwo-DimensionalRigidityPercolationThe.PDFVIP

JOURNAL OF COMPUTATIONAL PHYSICS 137, 346–365 (1997) ARTICLE NO. CP975809 An Algorithm for Two-Dimensional Rigidity Percolation: The Pebble Game Donald J. Jacobs* and Bruce Hendrickson† *Department of Physics and Astronomy, Michigan State University, East Lansing, Michigan 48824; and †Applied and Numerical Math, Sandia National Laboratories, Albuquerque, New Mexico 87185-1110 E-mail: *jacobs@pa.msu.edu and †bah@cs.sandia.gov Received July 19, 1996; revised June 9, 1997 Many important macroscopic properties of materials depend upon the number of microscopic degrees of freedom. The task of counting the number of such degrees of freedom can be computationally very expensive. We de- scribe a new approach for this calculation which is appropriate for two- dimensional, glass-like networks, building upon recent work in graph rigidity. This purely combinatorial algorithm is formulated in terms of a simple pebble game. It has allowed for the first studies of the rigidity transition in generic networks, which are models of amorphous materials and glasses. In the context of generic rigidity percolation, we show how to calculate the number of internal degrees of freedom, identify all rigid clusters, and locate the overcon- strained regions. For a network of n sites the pebble game has a worst case performance of O(n2). In our applications its performance scaled as n 1.15 at the rigidity transition, while away from the transition region it grew linearly. 1997 Academic Press Key Words: rigidity percolation; graph rigidity; graph algorithm; vector percolation; floppy modes; network glass.