AN ALGORITHM FOR 2-DIMENSIONAL RIGIDITY PERCOLATION - THE PEBBLE GAME

Many important macroscopic properties of materials depend upon the num ber of microscopic degrees of freedom. The task of counting the number of such degrees of freedom can be computationally very expensive. We describe a new approach for this calculation which is appropriate for two-dimensional, glass-like networks, building upon recent work in gra ph rigidity. This purely combinatorial algorithm is formulated in term s of a simple pebble game. It has allowed for the first studies of the rigidity transition in generic networks. which are models of amorphou s materials and glasses. In the context of generic rigidity percolatio n, we show how to calculate the number of internal degrees of freedom, identify all rigid clusters, and locate the overconstrained regions. For a network of rr sites the pebble game has a worst case performance of O(n(2)). In our applications its performance scaled as n(1.15) at the rigidity transition, while away from the transition region it grew linearly. (C) 1997 Academic Press.