×

zbMATH — the first resource for mathematics

Lower bounds on the number of realizations of rigid graphs. (English) Zbl 1442.05044
Summary: Computing the number of realizations of a minimally rigid graph is a notoriously difficult problem. Toward this goal, for graphs that are minimally rigid in the plane, we take advantage of a recently published algorithm, which is the fastest available method, although its complexity is still exponential. Combining computational results with the theory of constructing new rigid graphs by gluing, we give a new lower bound on the maximal possible number of (complex) realizations for graphs with a given number of vertices. We extend these ideas to rigid graphs in three dimensions and we derive similar lower bounds, by exploiting data from extensive Gröbner basis computations.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C85 Graph algorithms (graph-theoretic aspects)
68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
Software:
FGb
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Borcea, [Borcea and Streinu 04] C.; Streinu, I., The Number of Embeddings of Minimally Rigid Graphs., Discrete. Comput. Geom., 31, 287-303 (2004) · Zbl 1050.05030
[2] Capco, [Capco et al. 16] J.; Gallet, M.; Grasegger, G.; Koutschan, C.; Lubbes, N.; Schicho, J., Electronic Supplementary Material for the Paper “The Number of Realizations of a Laman Graph (2016)
[3] Capco, [Capco et al. 17a] J.; Gallet, M.; Grasegger, G.; Koutschan, C.; Lubbes, N.; Schicho, J., Computing the Number of Realizations of a Laman Graph., Electr. Notes Discr. Math., 61, 207-213 (2017) · Zbl 1378.05030
[4] Capco, [Capco et al. 17b] J.; Gallet, M.; Grasegger, G.; Koutschan, C.; Lubbes, N.; Schicho, J., The Number of Realizations of a Laman Graph, SIAM J. Appl. Alg. Geom. (2017) · Zbl 1378.05030
[5] Cruickshank, [Cruickshank 14] J., On Spaces of Infinitesimal Motions and Three Dimensional Henneberg Extensions, Discrete Comput. Geom., 51, 3, 702-721 (2014) · Zbl 1303.52011
[6] Emiris, [Emiris and Moroz 11] I. Z.; Moroz, G., The Assembly Modes of Rigid 11-bar Linkages (2011)
[7] Emiris, [Emiris and Mourrain 99] I. Z.; Mourrain, B., Computer Algebra Methods for Studying and Computing Molecular Conformations., Algorithmica, Spec. Issue Algo. Comput. Biol., 25, 372-402 (1999)
[8] Emiris, [Emiris et al. 13] I. Z.; Tsigaridas, E. P.; Varvitsiotis, A.; Mucherino, A.; Lavor, C.; Liberti, L.; Maculan, N., Distance Geometry, Mixed Volume and Distance Geometry Techniques for Counting Euclidean Embeddings of Rigid Graphs, 23-45 (2013), New York: Springer, New York · Zbl 1269.05077
[9] Emiris, [Emiris et al. 09] I. Z.; Tsigaridas, E. P.; Varvitsiotis, A. E.; Eppstein, D.; Gamsners, E. R., Graph Drawing: 17th International Symposium, Algebraic Methods for Counting Euclidean Embeddings of Graphs, 195-200 (2009), New York: Springer, New York
[10] Emmerich, [Emmerich 88] D. G., Structures tendues et autotendantes (1988)
[11] Faugère, [Faugère 10] J. C.; Fukuda, K.; van der Hoeven, J.; Joswig, M.; Takayama, N., Mathematical Software - ICMS 2010, volume 6327 of Lecture Notes in Computer Science, FGb: A Library for Computing Gröbner Bases, 84-87 (2010), Berlin Heidelberg: Springer, Berlin Heidelberg · Zbl 1294.68156
[12] Faugère, [Faugère and Lazard 95] J. C.; Lazard, D., The Combinatorial Classes of Parallel Manipulators Combinatorial Classes of Parallel Manipulators, Mech. Mach. Theo., 30, 6, 765-776 (1995)
[13] Graver, [Graver et al. 93] J.; Servatius, B.; Servatius, H., Combinatorial Rigidity (1993), Providence, RI: American Mathematical Society, Providence, RI
[14] Henneberg, [Henneberg 03] L.; Klein, F.; Müler, C., Encyklopädie der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen, IV, Die graphische Statik der starren Körper, 345-434 (1903)
[15] Jackson, [Jackson and Owen 18] B.; Owen, J. C., Disc. Appl. Math., Equivalent Realisations of A Rigid Graph (2018) · Zbl 1405.05037
[16] Jacobs, [Jacobs et al. 01] D. J.; Rader, A. J.; Kuhn, L. A.; Thorpe, M. F., Protein Flexibility Predictions using Graph Theory, Prot. Struct. Funct. Genet., 44, 2, 150-165 (2001)
[17] Laman, [Laman 70] G., On Graphs and Rigidity of Plane Skeletal Structures., J. Eng. Math., 4, 331-340 (1970) · Zbl 0213.51903
[18] Liberti, [Liberti et al. 11] L.; Lavor, C.; Mucherino, A.; Maculan, N., Molecular Distance Geometry Methods: From Continuous to Discrete, Int. Trans. Operat. Res., 18, 1, 33-51 (2011) · Zbl 1219.90177
[19] Liberti, [Liberti et al. 14] L.; Masson, B.; Lee, J.; Lavor, C.; Mucherino, A., On the Number of Realizations of Certain Henneberg Graphs Arising in Protein Conformation., Disc. Appl. Math., 165, 213-232 (2014) · Zbl 1288.05121
[20] Mucherino, [Mucherino et al. 12] A.; Lavor, C.; Liberti, L.; Maculan, N., Distance Geometry: Theory, Methods, and Applications (2012), New York: Springer Science & Business Media, New York
[21] Pollaczek-Geiringer, [Pollaczek-Geiringer 27] H., Über die Gliederung ebener Fachwerke, Z. Angew. Math. Mech. (ZAMM), 7, 1, 58-72 (1927) · JFM 53.0743.02
[22] Pollaczek-Geiringer, [Pollaczek-Geiringer 32] H., Zur Gliederungstheorie räumlicher Fachwerke, Z. Angew. Math. Mech. (ZAMM), 12, 6, 369-376 (1932) · JFM 58.1265.09
[23] Steffens, [Steffens and Theobald 10] R.; Theobald, T., Mixed Volume Techniques for Embeddings of Laman Graphs, Comput. Geom., 43, 2, 84-93 (2010) · Zbl 1225.05186
[24] Tay, [Tay and Whiteley 85] T.-S.; Whiteley, W., Generating Isostatic Frameworks., Topol. Struct., 11, 21-69 (1985) · Zbl 0574.51025
[25] Walter, [Walter and Husty 07a] D.; Husty, M. L., On a 9-bar Linkage, its Possible Configurations and Conditions for Paradoxical Mobility (2007)
[26] Walter, [Walter and Husty 07b] D.; Husty, M. L., A Spatial 9-bar Linkage, Possible Configurations and Conditions for Paradoxical Mobility, 195-208 (2007)
[27] Zhu, [Zhu 10] Z.; So, A. M.-C.; Ye, Y., Universal Rigidity and Edge Sparsification for Sensor Network Localization, SIAM J. Optim., 20, 6, 3059-3081 (2010) · Zbl 1211.90166
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.