Open Access. Powered by Scholars. Published by Universities.®
![Digital Commons Network](http://assets.bepress.com/20200205/img/dcn/DCsunburst.png)
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Graded Sparse Graphs And Matroids, Audrey Lee, Ileana Streinu, Louis Theran
Graded Sparse Graphs And Matroids, Audrey Lee, Ileana Streinu, Louis Theran
Computer Science: Faculty Publications
Sparse graphs and their associated matroids play an important role in rigidity theory, where they capture the combinatorics of some families of generic minimally rigid structures. We define a new family called graded sparse graphs, arising from generically pinned bar-and-joint frameworks, and prove that they also form matroids. We also address several algorithmic problems on graded sparse graphs: Decision, Spanning, Extraction, Components, Optimization, and Extension. We sketch variations on pebble game algorithms to solve them.