### Pebble Game Algorithms and (k,l)-Sparse Graphs

*Audrey Lee, Ileana Streinu*

#### Abstract

A multi-graph G on n vertices is (k,l)-sparse if every subset of n'≤n vertices spans at most kn'-l edges, 0 ≤l < 2k. G is

*tight*if, in addition, it has exactly kn - l edges. We characterize (k,l)-sparse graphs via a family of simple, elegant and efficient algorithms called the (k,l)-pebble games. As applications, we use the pebble games for computing*components*(maximal tight subgraphs) in sparse graphs, to obtain inductive (Henneberg) constructions, and, when l=k, edge-disjoint tree decompositions.Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page