Graded sparse graphs and matroids

Authors: Audrey Lee, Ileana Streinu, and Louis Theran
Journal: Journal of Universal Computer Science, 13111671–1679, 2007.
Full text: arXiv DOI

Sparse graphs and their associated matroids play an important role in rigidity theory, where they capture the combinatorics of generically rigid structures. We define a new family called graded sparse graphs, arising from generically pinned (completely immobilized) bar-and-joint frameworks and prove that they also form matroids. We address five problems on graded sparse graphs: Decision, Extraction, Components, Optimization, and Extension. We extend our pebble game algorithms to solve them.