72 citations · 250 across the 57 of their papers we have counts for
6 papers · 1 filter
Graded Sparse Graphs and Matroids
Audrey Lee, Ileana Streinu, Louis Theran
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…
Slider-pinning Rigidity: a Maxwell-Laman-type Theorem
Ileana Streinu, Louis Theran
We define and study slider-pinning rigidity, giving a complete combinatorial characterization. This is done via direction-slider networks, which are a generalization of Whiteley's…
Natural realizations of sparsity matroids
Ileana Streinu, Louis Theran
A hypergraph G with n vertices and m hyperedges with d endpoints each is (k,l)-sparse if for all sub-hypergraphs G' on n' vertices and m' edges, m'\le kn'-l. For integers k and l s…
Characterizing Sparse Graphs by Map Decompositions
Ruth Haas, Audrey Lee, Ileana Streinu +1
A {\bf map} is a graph that admits an orientation of its edges so that each vertex has out-degree exactly 1. We characterize graphs which admit a decomposition into edge-disjoi…
Sparsity-certifying Graph Decompositions
Ileana Streinu, Louis Theran
We describe a new algorithm, the -pebble game with colors, and use it obtain a characterization of the family of -sparse graphs and algorithmic solutions to a f…
Sparse Hypergraphs and Pebble Game Algorithms
Ileana Streinu, Louis Theran
A hypergraph is -sparse if no subset spans more than hyperedges. We characterize -sparse hypergraphs in terms of graph theo…