An algorithm for two-dimensional rigidity percolation: The pebble game (Q1375495)

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 overconstrained regions. For a network of \(n\) 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.