Pebble game algorithms and sparse graphs Original Research Article

A multi-graph G on n vertices is image-sparse if every subset of image vertices spans at most image edges. G is tight if, in addition, it has exactly image edges. For integer values k and image, we characterize the image-sparse graphs via a family of simple, elegant and efficient algorithms called the image-pebble games.