Pebble game algorithms and sparse graphs

A multi-graph G on n   vertices is (k,ℓ)(k,ℓ)-sparse if every subset of n′⩽nn′⩽n vertices spans at most kn′-ℓkn′-ℓ edges. G is tight   if, in addition, it has exactly kn-ℓkn-ℓ edges. For integer values k   and ℓ∈[0,2k)ℓ∈[0,2k), we characterize the (k,ℓ)(k,ℓ)-sparse graphs via a family of simple, elegant and efficient algorithms called the (k,ℓ)(k,ℓ)-pebble games.