Pebble Game Algorithms and Sparse Graphs

Abstract

A multi-graph $G$ on $n$ vertices is $(k,\ell )$-sparse if every subset of $n^{\prime }\le n$ vertices spans at most $k{n}^{\prime }-\ell$ edges. $G$ is {\em tight} if, in addition, it has exactly $kn-\ell$ edges. For integer values $k$ and $\ell \in [0,2k)$, we characterize the $(k,\ell )$-sparse graphs via a family of simple, elegant and efficient algorithms called the $(k,\ell )$-pebble games.

20 pages, abstract presented at EuroComb '05