On the number of embeddings of minimally rigid graphs

ABSTRACT

(MATH) Rigid frameworks in some Euclidian space are embedded graphs having a unique local realization (up to Euclidian motions) for the given edge lengths, although globally they may have several. We study first the number of distinct planar embeddings of rigid graphs with n vertices. We show that, modulo planar rigid motions, this number is at most $2n-4\choose n-2 \approx 4ⁿ. We also exhibit several families which realize lower bounds of the order of 2ⁿ, 2.21ⁿ and 2.88ⁿ.(MATH) For the upper bound we use techniques from complex algebraic geometry, based on the (projective) Cayley-Menger variety CM ^2,n(C)\subset P_n\choose 2-1(C)$ over the complex numbers C. In this context, point configurations are represented by coordinates given by squared distances between all pairs of points. Sectioning the variety with 2n-4 hyperplanes yields at most deg(CM ^2,n) zero-dimensional components, and one finds this degree to be D ^2,n =\frac122n-4\choose n-2$. The lower bounds are related to inductive constructions of minimally rigid graphs via Henneberg sequences.(MATH) The same approach works in higher dimensions. In particular we show that it leads to an upper bound of 2 D^3,n= \frac2^n-3n-2n-6\choosen-3$ for the number of spatial embeddings with generic edge lengths of the $1$-skeleton of a simplicial polyhedron, up to rigid motions.

REFERENCES

• 1: Saugata Basu, Different bounds on the different Betti numbers of semi-algebraic sets, Proceedings of the seventeenth annual symposium on Computational geometry, p.288-292, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378705]
• 2: Basu, Saugata and Pollack, Richard and Roy, Marie-Francoise. Algorithms in Real Algebraic Geometry, book, in preparation.
• 3: Berger, Marcel. Geometry I and II, Springer Verlag, 1987.
• 4: Blumenthal, Leonard. Theory and Applications of Distance Geometry, Chelsea, Bronx NY, 1970.
• 5: Borcea, Ciprian. Point Configurations and Cayley-Menger Varieties, manuscript, submitted, 2001.
• 6: John F. Canny, The complexity of robot motion planning, MIT Press, Cambridge, MA, 1988
• 7: Connelly, Robert. Rigidity, in P. M. Gruber and J. M. Wills (eds.) Handbook of Convex Geometry, vol. A, North Holland, 1993, pp. 22--272.
• 8: Crippen, G. M. Distance Geometry and Conformational Calculations. Research Studies Press, John Wiley, 1981.
• 9: Crippen, G. M. and Havel, T. F. Distance Geometry and Molecular Conformation. Research Studies Press, John Wiley, 1988.
• 10: Deza, Michel Marie and Laurent, Monique. Geometry of Cuts and Metrics. Springer Verlag, 1997.
• 11: Fulton, William. Intersection theory, Springer-Verlag, 1984.
• 12: Giambelli, G.Z. Sulle varietá rappresentate coll'annullare determinanti minori contenuti in un determinante simmetrico od emisimmetrico generico di forme. Atti della R. Acc. Sci. di Torino 44 (1905/1906), 102--125.
• 13: Gluck, Hermann. Almost all simply connected closed surfaces are rigid, in Geometric Topology, Lecture Notes in Mathematics No. 438, Springer Verlag, Berlin, 1975, pp. 225--239.
• 14: Graver, Jack and Servatius, Brigitte and Servatius, Hermann. Combinatorial Rigidity, Amer. Math. Soc., Graduate Studies in Mathematics vol.2, 1993.
• 15: Harris, Joe. Algebraic Geometry, Graduate Texts in Math. 133, Springer-Verlag, 1993.
• 16: Harris, Joe and Tu, L.W. On symmetric and skew-symmetric determinantal varieties, Topology 23, 1984, pp. 71--84.
• 17: Bruce Hendrickson, Conditions for unique graph realizations, SIAM Journal on Computing, v.21 n.1, p.65-84, Feb. 1992 [doi>10.1137/0221008]
• 18: Bruce Alan Hendrickson, The molecule problem: determining conformation from pairwise distances, Cornell University, Ithaca, NY, 1991
• 19: Henneberg, L. Die graphische Statik der starren Systeme, Leipzig, 1911.
• 20: Hrones, J. A. and Nelson, G. I. Analysis of the Fourbar Linkage, MIT Technology Press, Cambridge, MA, 1951.
• 21: Józefiak, T., Lascoux, A. and Pragacz, P. Classes of determinantal varieties associated with symmetric and skew-symmetric matrices. Math. USSR Izvestija 18 (1982), 575--586.
• 22: Laman, G. On graphs and rigidity of plane skeletal structures. Eng. Math., 4, 331--340, 1970.
• 23: Milnor, John. On the Betti numbers of real varieties, Proc. AMS 15, 1964, pp. 275--280.
• 24: Norton, Robert L. Design of Machinery. McGraw Hill, 2nd ed. 2001.
• 25: Oleinik, O. A. and Petrovskii, I. B. On the topology of real algebraic surfaces, Izv. Akad. Nauk SSSR 13, 1949, pp. 389--402.
• 26: Richter-Gebert, Jürgen and Kortenkamp, Ulrich. Cinderella, an interactive software package for Geometry, Springer Verlag, 1999.
• 27: Saxe, J. B. Embedability of weighted graphs in k-space is strongly NP-hard, in Proc. Allerton Conf. on Communications, Control and Computing, 1979, pp. 480--489.
• 28: Steinitz, Ernest and H. Rademacher. Vorlesungen über die Theorie der Polyedern, Springer, Berlin, 1934.
• 29: Thom, René. Sur l'homologie des variétés réelles, Differential and Combinatorial Topology, pp. 255--265, Princeton University Press, Princeton, 1965.
• 30: Whiteley, Walter. Some Matroids from Discrete Applied Geometry, Contemporary Mathematics, vol. 197, pp. 171--311, Amer. Math. Soc. 1996.
• 31: Walter Whiteley, Rigidity and scene analysis, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 32: Whiteley, Walter. Rigidity of Molecular Structures, in Rigidity Theory and Applications, Kluwer, 1999.
• 33: Wunderlich, W. Hohere Koppelkurven, in Österiechisches Ingenieur Archiv, XVII(3), 1963, pp. 162--165.

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.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Theory

Keywords:
Cayley-Menger variety, distance geometry, graph embedding, lower bound, rigidity, upper bound