Graded Sparse Graphs and Matroids
From MaRDI portal
Publication:6207531
arXiv0711.2838MaRDI QIDQ6207531FDOQ6207531
Authors: Audrey Lee, Ileana Streinu, Louis Theran 
Publication date: 18 November 2007
Abstract: 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 {�f 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: {�f Decision}, {�f Extraction}, {�f Components}, {�f Optimization}, and {�f Extension}. We extend our {�f pebble game algorithms} to solve them.
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial aspects of matroids and geometric lattices (05B35)
This page was built for publication: Graded Sparse Graphs and Matroids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6207531)
