An algorithm for two-dimensional rigidity percolation: the pebble game

摘要

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.