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.