Combinatorial genericity and minimal rigidity

ABSTRACT

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 (or 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.

Several definitions (some but not all equivalent) of genericity appear in the rigidity literature, and they have either a measure theoretic, topologic or algebraic-geometric flavor. Some generic point sets appear to be highly degenerate, and still turn out to be generic. All existing proofs of Laman's Theorem make use at some point of one or another of these geometric genericity assumptions.

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.

REFERENCES

• 1: A. C. Aitken. Determinants and Matrices. Oliver and Boyd, Edinburgh, 1948.
• 2: L. Asimow and B. Roth. The rigidity of graphs. Transactions of the American Mathematical Society, 245:279--289, November 1978.
• 3: S. Bereg. Faster algorithms for rigidity in the plane. http://arxiv.org/abs/0711.2835, 2007.
• 4: H. H. Crapo. On the generic rigidity of plane frameworks. Technical Report 1278, Institut de recherche d'informatique et d'automatique, 1988.
• 5: G. M. Crippen and T. F. Havel. Distance Geometry and Molecular Conformation. John Wiley and Research Studies Press, Somerset, England, 1988.
• 6: O. Daescu and A. Kurdia. Recognizing minimally rigid graphs in the plane in subquadratic time. In The Proceedings of the 17th Fall Workshop on Computational and Combinatorial Geometry (FWCG '07), 2007. http://linkage.cs.umass.edu/fwcg2007/Proceedings/submission_25.pdf.
• 7: Z. Fekete. Source location with rigidity and tree packing requirements. Operations Research Letters, 34(6):607--612, November 2006.
• 8: H. Gabow and H. H. Westermann. Forests, frames, and games: Algorithms for matroid sums and applications. Algorithmica, 7(1):465--497, December 1992.
• 9: I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky. Discriminants, Resultants and Multidimensional Determinants. Birkhäuser, Boston, 1994.
• 10: H. Gluck. Almost all simply connected closed surfaces are rigid. Lecture Notes in Matehmatics, 438:225--239, 1975.
• 11: J. Graver, B. Servatius, and H. Servatius. Combinatorial rigidity, volume 2 of Graduate Studies in Mathematics. American Mathematical Society, November 1993.
• 12: R. Haas. Characterizations of arboricity of graphs. Ars Combinatorica, 63:129--137, 2002.
• 13: R. Haas, A. Lee, I. Streinu, and L. Theran. Characterizing sparse graphs by map decompositions. Journal of Combinatorial Mathematics and Combinatorial Computing, 62:3--11, 2007.
• 14: L. Henneberg. Die graphische statik der starren systeme. Johnson Reprint 1968. Leipzig, 1911.
• 15: Donald J. Jacobs , Bruce Hendrickson, An algorithm for two-dimensional rigidity percolation: the pebble game, Journal of Computational Physics, v.137 n.2, p.346-365, Nov. 1, 1997 [doi>10.1006/jcph.1997.5809]
• 16: G. Laman. On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics, 4:331--340, 1970.
• 17: A. Lee and I. Streinu. Pebble game algorithms and sparse graphs. Discrete Mathematics, 2007. http://dx.doi.org/10.1016/j.disc.2007.07.104.
• 18: A. Lee, I. Streinu, and L. Theran. Finding and maintaining rigid components. In Proceeding of the Canadian Conference of Computational Geometry. Windsor, Ontario, 2005. http://cccg.cs.uwindsor.ca/papers/72.pdf.
• 19: A. Lee, I. Streinu, and L. Theran. Graded sparse graphs and matroids. Journal of Universal Computer Science, 13(10), 2007.
• 20: A. Lee, I. Streinu, and L. Theran. The slider-pinning problem. In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG'07), 2007.
• 21: L. Lovász and M. D. Plummer. Matching Theory, volume 29 of Annals of Discrete Mathematics. North Holland, 1986.
• 22: L. Lovász and Y. Yemini. On generic rigidity in the plane. SIAM J. Algebraic and Discrete Methods, 3(1):91--98, 1982.
• 23: L. Lovász. The matroid matching problem. Algebraic methods in graph theory, 25:495--517, 1978.
• 24: L. Lovász. Matroid matching and some applications. Journal of Combinatorial Theory, Series (B), 28:208--236, 1980.
• 25: J. C. Maxwell. On the calculation of the equilibrium and stiffness of frames. Philos. Mag., 27:294, 1864.
• 26: C. S. A. Nash-Williams. Decomposition of finite graphs into forests. Journal London Mathematical Society, 39:12, 1964.
• 27: J. G. Oxley. Matroid theory. The Clarendon Press Oxford University Press, New York, 1992.
• 28: A. Recski. A network theory approach to the rigidity of skeletal structures II. Laman's theorem and topological formulae. Discrete Applied Math, 8:63--68, 1984.
• 29: J. B. Saxe. Embeddability of weighted graphs in k-space is strongly np-hard. In Proc. of 17th Allerton Conference in Communications, Control, and Computing, pages 480--489, Monticello, IL, 1979.
• 30: Anthony Man-Cho So , Yinyu Ye, Theory of semidefinite programming for sensor network localization, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 31: I. Streinu and L. Theran. Combinatorial genericity and minimal rigidity. 2007. http://arxiv.org/abs/0712.0031.
• 32: I. Streinu and L. Theran. Sparsity-certifying graph decompositions. http://arxiv.org/abs/0704.0002, 2007.
• 33: T.-S. Tay. A new proof of Laman's theorem. Graphs and Combinatorics, 9:365--370, 1993.
• 34: W. T. Tutte. On the problem of decomposing a graph into n connected factors. Journal London Math. Soc., 142:221--230, 1961.
• 35: Walter Whiteley, The union of matroids and the rigidity of frameworks, SIAM Journal on Discrete Mathematics, v.1 n.2, p.237-255, May 1988 [doi>10.1137/0401025]
• 36: W. Whiteley. Some matroids from discrete applied geometry. In J. Bonin, J. G. Oxley, and B. Servatius, editors, Matroid Theory, volume 197 of Contemporary Mathematics, pages 171--311. American Mathematical Society, 1996.
• 37: Walter Whiteley, Rigidity and scene analysis, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Theory

Keywords:
computational geometry, rigidity, sparse graphs