Ciprian Borcea
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 4n. We also exhibit several families which realize lower bounds of the order of 2n, 2.21n and 2.88n.(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.
- Basu, Saugata. Different Bounds on the Different Betti Numbers of Semi-Algebraic Sets, Proc. 17th Symp. on Comput. Geometry (SoCG), Medford, Massachusetts, 2001, pp. 288--292. Google Scholar
Digital Library
- Basu, Saugata and Pollack, Richard and Roy, Marie-Francoise. Algorithms in Real Algebraic Geometry, book, in preparation. Google ScholarDigital Library
- Berger, Marcel. Geometry I and II, Springer Verlag, 1987.Google Scholar
- Blumenthal, Leonard. Theory and Applications of Distance Geometry, Chelsea, Bronx NY, 1970.Google Scholar
- Borcea, Ciprian. Point Configurations and Cayley-Menger Varieties, manuscript, submitted, 2001.Google Scholar
- Canny, John. Complexity of Robot Motion Planning, MIT Press, Cambridge, MA, 1988. Google ScholarDigital Library
- Connelly, Robert. Rigidity, in P. M. Gruber and J. M. Wills (eds.) Handbook of Convex Geometry, vol. A, North Holland, 1993, pp. 22--272.Google Scholar
- Crippen, G. M. Distance Geometry and Conformational Calculations. Research Studies Press, John Wiley, 1981.Google Scholar
- Crippen, G. M. and Havel, T. F. Distance Geometry and Molecular Conformation. Research Studies Press, John Wiley, 1988.Google Scholar
- Deza, Michel Marie and Laurent, Monique. Geometry of Cuts and Metrics. Springer Verlag, 1997.Google ScholarCross Ref
- Fulton, William. Intersection theory, Springer-Verlag, 1984.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- Graver, Jack and Servatius, Brigitte and Servatius, Hermann. Combinatorial Rigidity, Amer. Math. Soc., Graduate Studies in Mathematics vol.2, 1993.Google Scholar
- Harris, Joe. Algebraic Geometry, Graduate Texts in Math. 133, Springer-Verlag, 1993.Google Scholar
- Harris, Joe and Tu, L.W. On symmetric and skew-symmetric determinantal varieties, Topology 23, 1984, pp. 71--84.Google ScholarCross Ref
- Hendrickson, Bruce. Conditions for unique graph realizations, SIAM J. Comput., 21(1), pp. 65--84, 1992. Google ScholarDigital Library
- Hendrickson, Bruce. The Molecule Problem: Determining Conformation from Pairwise Distances, PhD Thesis, Computer Science Department, Cornell University. Technical Report 90-1159. Google ScholarDigital Library
- Henneberg, L. Die graphische Statik der starren Systeme, Leipzig, 1911.Google Scholar
- Hrones, J. A. and Nelson, G. I. Analysis of the Fourbar Linkage, MIT Technology Press, Cambridge, MA, 1951.Google Scholar
- 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.Google ScholarCross Ref
- Laman, G. On graphs and rigidity of plane skeletal structures. Eng. Math., 4, 331--340, 1970.Google ScholarCross Ref
- Milnor, John. On the Betti numbers of real varieties, Proc. AMS 15, 1964, pp. 275--280.Google ScholarCross Ref
- Norton, Robert L. Design of Machinery. McGraw Hill, 2nd ed. 2001.Google Scholar
- Oleinik, O. A. and Petrovskii, I. B. On the topology of real algebraic surfaces, Izv. Akad. Nauk SSSR 13, 1949, pp. 389--402.Google Scholar
- Richter-Gebert, Jürgen and Kortenkamp, Ulrich. Cinderella, an interactive software package for Geometry, Springer Verlag, 1999.Google Scholar
- 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.Google Scholar
- Steinitz, Ernest and H. Rademacher. Vorlesungen über die Theorie der Polyedern, Springer, Berlin, 1934.Google Scholar
- Thom, René. Sur l'homologie des variétés réelles, Differential and Combinatorial Topology, pp. 255--265, Princeton University Press, Princeton, 1965.Google ScholarCross Ref
- Whiteley, Walter. Some Matroids from Discrete Applied Geometry, Contemporary Mathematics, vol. 197, pp. 171--311, Amer. Math. Soc. 1996.Google ScholarCross Ref
- Whiteley, Walter. Rigidity and Scene Analysis, in Handbook of Discrete and Computational Geometry, (Jacob E. Goodman, Joseph O'Rourke, eds.), 1997, pp. 893--916. Google ScholarDigital Library
- Whiteley, Walter. Rigidity of Molecular Structures, in Rigidity Theory and Applications, Kluwer, 1999.Google Scholar
- Wunderlich, W. Hohere Koppelkurven, in Österiechisches Ingenieur Archiv, XVII(3), 1963, pp. 162--165.Google Scholar
Index Terms
- On the number of embeddings of minimally rigid graphs
Recommendations
New Upper Bounds for the Number of Embeddings of Minimally Rigid Graphs
AbstractBy definition, a rigid graph in (or on a sphere) has a finite number of embeddings up to rigid motions for a given set of edge length constraints. These embeddings are related to the real solutions of an algebraic system. Naturally, the complex ...
Restrained domination in cubic graphs
Let G =( V , E ) be a graph. A set S V is a restrained dominating set if every vertex in V S is adjacent to a vertex in S and to a vertex in V S . The restrained domination number of G , denoted r ( G ), is the smallest ...
On the Maximal Number of Real Embeddings of Spatial Minimally Rigid Graphs
ISSAC '18: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic ComputationThe number of embeddings of minimally rigid graphs in RD is (by definition) finite, modulo rigid transformations, for every generic choice of edge lengths. Even though various approaches have been proposed to compute it, the gap between upper and lower ...
Comments