Pebble Game

In rigidity theory and sparse graph algorithms, a pebble game is an algorithm that uses pebbles as movable markers to certify graph sparsity. The (k,l)-pebble games characterize and recognize graphs for which every subset of n^' vertices spans at most kn^'-l edges. The case in which equality holds for the whole graph is called tight. In particular, the (2,3)-tight case recognizes Laman graphs, which are the minimally rigid graphs in the plane by Laman's theorem (Lee and Streinu 2008).

This use of the term is distinct from graph pebbling, in which pebbling moves consume pebbles in transit and lead to invariants such as the pebbling number.

See also

Explore with Wolfram|Alpha

References

Cite this as:

Weisstein, Eric W. "Pebble Game." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PebbleGame.html

Subject classifications