A multi-graph G on n vertices is (k, l)-sparse if every subset of n'≤ n vertices spans at most kn'-l edges. G is tight if, in addition, it has exactly kn-l edges. For integer values k and l∈ [0, 2k), we characterize the (k, l)-sparse graphs via a family of simple, elegant and efficient algorithms called the (k, l)-pebble games.
A well studied geometric problem, with applications ranging from molecular structure determination to sensor networks, asks for the reconstruction of a set P of n unknown points from a finite set of pairwise distances (up to Euclidean isometries). We are concerned here with a related problem: which sets of distances are minimal with the property that they allow for the reconstruction of P, up to a finite set of possibilities? In the planar case, the answer is known generically via the landmark Maxwell-Laman Theorem from Rigidity Theory, and it leads to a combinatorial answer: the underlying structure of such a generic minimal collection of distances is a minimally rigid (aka Laman) graph, for which very efficient combinatorial decision algorithms exist. For non-generic cases the situation appears to be dramatically different, with the best known algorithms relying on exponential-time Gröbner base methods, and some specific instances known to be NP-hard. Understanding what makes a point set generic emerges as an intriguing geometric question with practical algorithmic consequences.
The main result of this paper is the first purely combinatorial proof of Laman's theorem, together with some interesting consequences. Genericity is characterized in terms of a certain determinant being not identically-zero as a formal polynomial. We relate its monomial expansion to certain colorings and orientations of the graph and show that these terms cannot all cancel exactly when the underlying graph is Laman. As a surprising consequence, genericity emerges as a purely combinatorial concept.
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 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: Decision, Extraction, Components, Optimization, and Extension. We extend our pebble game algorithms to solve them.
A Laman mechanism is a flexible planar bar-and-joint framework with m ≤ 2n − 3 edges and exactly k = 2n − m degrees of freedom. The slider-pinning problem is to eliminate all the degrees of freedom of a Laman mechanism, in an optimal fashion, by individually fixing x- or y-coordinates of vertices. We describe two easy to implement O(n^2) time algorithms.
We describe a new algorithm, the (k, l)-pebble game with colors, and use it obtain a characterization of the family of (k, l)-sparse graphs and algorithmic solutions to a family of problems concerning tree decompositions of graphs. Special instances of sparse graphs appear in rigidity theory and have received increased attention in recent years. In particular, our colored pebbles generalize and strengthen the previous results of Lee and Streinu and give a new proof of the Tutte-Nash-Williams characterization of arboricity. We also present a new decomposition that certifies sparsity based on the (k, l)-pebble game with colors. Our work also exposes connections between pebble game algorithms and previous sparse graph algorithms by Gabow, Gabow and Westermann and Hendrickson.
A hypergraph G=(V,E) is (k, l)-sparse if no subset V⊂V spans more than k|V'|-l hyperedges. We characterize (k, l)-sparse hypergraphs in terms of graph theoretic, matroidal and algorithmic properties. We extend several well-known theorems of Haas, Lovász, Nash-Williams, Tutte, and White and Whiteley, linking arboricity of graphs to certain counts on the number of edges. We also address the problem of finding lower-dimensional representations of sparse hypergraphs, and identify a critical behaviour in terms of the sparsity parameters k and l. Our constructions extend the pebble games of Lee and Streinu from graphs to hypergraphs.
We give the first complete analysis that the complexity of finding and maintaining rigid components of planar bar-and-joint frameworks and arbitrary d-dimensional body-and-bar frameworks, using a family of algorithms called pebble games, is O(n^2 ). To this end, we introduce a new data structure problem called union pair-find, which maintains disjoint edge sets and supports pair-find queries of whether two vertices are spanned by a set.
We present solutions that apply to generalizations of the pebble game algorithms, beyond the original rigidity motivation.