JUCS - Journal of Universal Computer Science 13(11): 1671-1679, doi: 10.3217/jucs-013-11-1671
Graded Sparse Graphs and Matroids
expand article infoAudrey Lee‡, Ileana Streinu§, Louis Theran‡
‡ University of Massachusetts, Amherst, United States of America§ Smith College, Northampton, United States of America

Corresponding author: Audrey Lee ( alee@cs.umass.edu )

© Audrey Lee, Ileana Streinu, Louis Theran.
This article is freely available under the J.UCS Open Content License.
Citation: Lee A, Streinu I, Theran L (2007) Graded Sparse Graphs and Matroids. JUCS - Journal of Universal Computer Science 13(11): 1671-1679. https://doi.org/10.3217/jucs-013-11-1671
Open Access
Abstract
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.
Keywords
computational geometry, hypergraph, rigidity theory, matroid, pebble game