Graded sparse graphs and matroids

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.