7 citations · 8 across the 4 of their papers we have counts for
6 papers · 1 filter
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…
Pebble Game Algorithms and Sparse Graphs
Audrey Lee, Ileana Streinu
A multi-graph on vertices is -sparse if every subset of vertices spans at most edges. is {\em tight} if, in addition, it has exactly $k…
Enumerating Constrained Non-crossing Minimally Rigid Frameworks
David Avis, Naoki Katoh, Makoto Ohsaki +2
In this paper we present an algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-and-joint frameworks under edge constraints (also cal…
Planar Minimally Rigid Graphs and Pseudo-Triangulations
Ruth Haas, David Orden, Guenter Rote +6
Pointed pseudo-triangulations are planar minimally rigid graphs embedded in the plane with pointed vertices (adjacent to an angle larger than 180 degrees. In this paper we prove th…
A Topological Representation Theorem for Oriented Matroids
Juergen Bokowski, Simon King, Susanne Mock +1
We present a new direct proof of a topological representation theorem for oriented matroids in the general rank case. Our proof is based on an earlier rank 3 version. It uses hyper…