https://hal.inria.fr/hal-01184350Lee, AudreyAudreyLeeDepartment of Computer Science [Amherst] - UMass Amherst - University of Massachusetts [Amherst] - UMASS - University of Massachusetts SystemStreinu, IleanaIleanaStreinuSmith College - Computer Science Department - Smith College [Northampton]Pebble Game Algorithms and (k,l)-Sparse GraphsHAL CCSD2005sparse graphpebble gamerigidityarboricitygraph orientation with bounded degree[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM][MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]Episciences Iam, CoordinationStefan Felsner2015-08-14 11:36:472019-11-18 12:12:022015-08-14 16:28:47enConference papershttps://hal.inria.fr/hal-01184350/document10.46298/dmtcs.3394application/pdf1A 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.