DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

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

Audrey Lee, Ileana Streinu


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

Valid XHTML 1.0 Transitional