Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 13 / Issue 11

available in:   PDF (133 kB) PS (143 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-013-11-1671


Graded Sparse Graphs and Matroids

Audrey Lee (University of Massachusetts, USA)

Ileana Streinu (Smith College, USA)

Louis Theran (University of Massachusetts, USA)

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, matroid, pebble game, rigidity theory

Categories: F.2.2, G.2.2