×

zbMATH — the first resource for mathematics

The number of realizations of a Laman graph. (English) Zbl 1439.14182

MSC:
14T15 Combinatorial aspects of tropical varieties
14N99 Projective and enumerative algebraic geometry
52C25 Rigidity and flexibility of structures (aspects of discrete geometry)
05C99 Graph theory
Software:
FGb; OEIS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] S. Bereg, Certifying and constructing minimally rigid graphs in the plane, in Proceedings of the Twenty-First Annual Symposium on Computational Geometry, ACM, New York, 2005, pp. 73–80, . · Zbl 1387.68238
[2] C. Borcea and I. Streinu, The number of embeddings of minimally rigid graphs, Discrete Comput. Geom., 31 (2004), pp. 287–303, . · Zbl 1050.05030
[3] C. Borcea and I. Streinu, Frameworks with crystallographic symmetry, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 372 (2013), 20120143, . · Zbl 1353.52019
[4] N. Bourbaki, Elements of Mathematics. Commutative Algebra, Springer-Verlag, Berlin, 1998. · Zbl 1101.13300
[5] N. Bourbaki, Algebra II. Chapters 4–7, Elements of Mathematics, Springer-Verlag, Berlin, 2003, .
[6] J. Capco, M. Gallet, G. Grasegger, C. Koutschan, N. Lubbes, and J. Schicho, Electronic supplementary material for the paper “The number of realizations of a Laman graph,” 2016, available at . · Zbl 1378.05030
[7] J. Capco, M. Gallet, G. Grasegger, C. Koutschan, N. Lubbes, and J. Schicho, Computing the number of realizations of a Laman graph, Electron. Notes Discrete Math., 61 (2017), pp. 207–213, . · Zbl 1378.05030
[8] R. Connelly, Rigidity, in Handbook of Convex Geometry, North-Holland, Amsterdam, 1993, pp. 223–271.
[9] H. Crapo, On the Generic Rigidity of Plane Frameworks, Tech. Report RR-1278, 00075281, HAL, INRIA, 2006, .
[10] O. Daescu and A. Kurdia, Towards an optimal algorithm for recognizing Laman graphs, J. Graph Algorithms Appl., 13 (2009), pp. 219–232, . · Zbl 1201.05092
[11] P. Dietmaier, The Stewart-Gough platform of general geometry can have \textup40 real postures, in Advances in Robot Kinematics: Analysis and Control, J. Lenarčič and M. Husty, eds., Springer, Dordrecht, The Netherlands, 1998, pp. 7–16, . · Zbl 0953.70006
[12] I. Emiris, E. Tsigaridas, and A. Varvitsiotis, Algebraic methods for counting Euclidean embeddings of graphs, in Graph Drawing: 17th International Symposium, D. Eppstein and E. Gamsner, eds., Springer, 2009, pp. 195–200, . · Zbl 1284.05137
[13] I. Emiris, E. Tsigaridas, and A. Varvitsiotis, Mixed volume and distance geometry techniques for counting Euclidean embeddings of rigid graphs, in Distance Geometry, Springer, New York, 2013, pp. 23–45, . · Zbl 1269.05077
[14] Z. Emiris and B. Mourrain, Computer algebra methods for studying and computing molecular conformations, Algorithmica, 25 (1999), pp. 372–402, .
[15] J.-C. Faugère, FGb: A library for computing Gröbner bases, in Mathematical Software - ICMS 2010, Lecture Notes in Comput. Sci. 6327, K. Fukuda, J. van der Hoeven, M. Joswig, and N. Takayama, eds., Springer, Berlin, Heidelberg, 2010, pp. 84–87, .
[16] J.-C. Faugère and D. Lazard, Combinatorial classes of parallel manipulators, Mech. Mach. Theory, 30 (1995), pp. 765–776, .
[17] S. J. Gortler, A. D. Healy, and D. P. Thurston, Characterizing generic global rigidity, Amer. J. Math., 132 (2010), pp. 897–939, . · Zbl 1202.52020
[18] J. Graver, B. Servatius, and H. Servatius, Combinatorial Rigidity, AMS, Providence, RI, 1993, . · Zbl 0788.05001
[19] L. Henneberg, Die graphische Statik der starren Körper, in Encyklopädie der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen, Vol. IV, 1903, pp. 345–434. · JFM 34.0748.12
[20] B. Jackson and J. C. Owen, Equivalent realisations of a rigid graph, Discrete Appl. Math., to appear, . · Zbl 1405.05037
[21] D. Jacobs and B. Hendrickson, An algorithm for two-dimensional rigidity percolation: The pebble game, J. Comput. Phys., 137 (1997), pp. 346–365, . · Zbl 0894.73004
[22] D. Jacobs, A. Rader, L. Kuhn, and M. Thorpe, Protein flexibility predictions using graph theory, Proteins: Structure, Function, and Bioinformatics, 44 (2001), pp. 150–165, .
[23] E. Katz, A tropical toolkit, Expo. Math., 27 (2009), pp. 1–36, . · Zbl 1193.14004
[24] G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math., 4 (1970), pp. 331–340, . · Zbl 0213.51903
[25] L. Liberti, B. Masson, J. Lee, C. Lavor, and A. Mucherino, On the number of realizations of certain Henneberg graphs arising in protein conformation, Discrete Appl. Math., 165 (2014), pp. 213–232, . · Zbl 1288.05121
[26] L. Lovász and Y. Yemini, On generic rigidity in the plane, SIAM J. Algebraic Discrete Methods, 3 (1982), pp. 91–98, . · Zbl 0497.05025
[27] D. Maclagan and B. Sturmfels, Introduction to Tropical Geometry, Grad. Stud. Math. 161, AMS, Providence, RI, 2015, . · Zbl 1321.14048
[28] G. Mikhalkin, Enumerative tropical algebraic geometry in \(\mathbb{R}^2\), J. Amer. Math. Soc., 18 (2005), pp. 313–377, . · Zbl 1092.14068
[29] S. Payne, Fibers of tropicalization, Math. Z., 262 (2009), pp. 301–311. · Zbl 1222.14130
[30] H. Pollaczek-Geiringer, Über die Gliederung ebener Fachwerke, ZAMM Z. Angew. Math. Mech., 7 (1927), pp. 58–72, . · JFM 53.0743.02
[31] O. Raz, Configurations of lines in space and combinatorial rigidity, Discrete Comput. Geom., 58 (2017), pp. 986–1009, . · Zbl 1381.52029
[32] A. Recski, A network theory approach to the rigidity of skeletal structures, part \textupII. Laman’s theorem and topological formulae, Discrete Appl. Math., 8 (1984), pp. 63–68, . · Zbl 0537.51028
[33] F. Ronga and T. Vust, Stewart platforms without computer?, in Real Analytic and Algebraic Geometry (Trento, 1992), de Gruyter, Berlin, 1995, pp. 197–212, . · Zbl 0827.70003
[34] Z. Rosen, Computing Algebraic Matroids, preprint, , 2014.
[35] J. Selig, Geometric Fundamentals of Robotics, 2nd ed., Monographs in Computer Science, Springer, New York, 2005, . · Zbl 1062.93002
[36] N. Sloane, The On-Line Encyclopedia of Integer Sequences, OEIS Foundation Inc., . · Zbl 1274.11001
[37] R. Steffens and T. Theobald, Mixed volume techniques for embeddings of Laman graphs, Comput. Geom., 43 (2010), pp. 84–93, . · Zbl 1225.05186
[38] B. Sturmfels, Solving Systems of Polynomial Equations, CBMS Reg. Conf. Ser. Math. 97, AMS, Providence, RI, 2002, .
[39] M. Thorpe and P. Duxbury, eds., Rigidity Theory and Applications, Springer, Boston, MA, 2002, .
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.