×

zbMATH — the first resource for mathematics

On the maximal number of real embeddings of minimally rigid graphs in \(\mathbb{R}^2,\mathbb{R}^3\) and \(S^2\). (English) Zbl 1448.05144
Summary: Rigidity theory studies the properties of graphs that can have rigid embeddings in a Euclidean space \(\mathbb{R}^d\) or on a sphere and other manifolds which in addition satisfy certain edge length constraints. One of the major open problems in this field is to determine lower and upper bounds on the number of realizations with respect to a given number of vertices. This problem is closely related to the classification of rigid graphs according to their maximal number of real embeddings.
In this paper, we are interested in finding edge lengths that can maximize the number of real embeddings of minimally rigid graphs in the plane, space, and on the sphere. We use algebraic formulations to provide upper bounds. To find values of the parameters that lead to graphs with a large number of real realizations, possibly attaining the (algebraic) upper bounds, we use some standard heuristics and we also develop a new method inspired by coupler curves. We apply this new method to obtain embeddings in \(\mathbb{R}^3\). One of its main novelties is that it allows us to sample efficiently from a larger number of parameters by selecting only a subset of them at each iteration.
Our results include a full classification of the 7-vertex graphs according to their maximal numbers of real embeddings in the cases of the embeddings in \(\mathbb{R}^2\) and \(\mathbb{R}^3\), while in the case of \(S^2\) we achieve this classification for all 6-vertex graphs. Additionally, by increasing the number of embeddings of selected graphs, we improve the previously known asymptotic lower bound on the maximum number of realizations. The methods and the results concerning the spatial embeddings are part of [E. Bartzos et al., in: Proceedings of the 43rd international symposium on symbolic and algebraic computation, ISSAC 2018, New York, NY, USA, July 16–19, 2018. New York, NY: Association for Computing Machinery (ACM). 55–62 (2018; Zbl 07245499)].
MSC:
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C62 Graph representations (geometric and intersection representations, etc.)
05C30 Enumeration in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bartzos, E.; Emiris, I.; Legerský, J.; Tsigaridas, E., On the maximal number of real embeddings of spatial minimally rigid graphs, (Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation. Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC ’18 (2018), ACM: ACM New York, NY, USA), 55-62, URL
[2] Bartzos, E.; Legerský, J., Graph embeddings in the plane, space and sphere — source code and results (2018), Zenodo. URL
[3] Bernstein, D., The number of roots of a system of equations, Funct. Anal. Appl., 9, 183-185 (1975) · Zbl 0328.32001
[4] Bihan, F.; Rojast, J. M.; Sottile, F., On the sharpness of fewnomial bounds and the number of components of fewnomial hypersurfaces, (Algorithms in Algebraic Geometry (2008), Springer), 15-20 · Zbl 1132.14334
[5] Bihan, F.; Santos, F.; Spaenlehauer, P.-J., A polyhedral method for sparse systems with many positive solutions (2018), arXiv preprint · Zbl 07026356
[6] Blumenthal, L. M., Theory and Applications of Distance Geometry (1970), Chelsea Publishing Company: Chelsea Publishing Company New York · Zbl 0208.24801
[7] Borcea, C. S., Point configurations and Cayley-Menger varieties (2002)
[8] Borcea, C. S.; Streinu, I., The number of embeddings of minimally rigid graphs, Discrete Comput. Geom., 2, 287-303 (2004) · Zbl 1050.05030
[9] Capco, J.; Gallet, M.; Grasegger, G.; Koutschan, C.; Lubbes, N.; Schicho, J., The number of realizations of a Laman graph, SIAM J. Appl. Algebra Geom., 2, 1, 94-125 (2018) · Zbl 1439.14182
[10] Connelly, R., Generic global rigidity, Discrete Comput. Geom., 33, 549-563 (2005) · Zbl 1072.52016
[11] Dattorro, M.; Dattorro, J., Convex Optimization & Euclidean Distance Geometry (2005)
[12] Dietmaier, P., The Stewart-Gough platform of general geometry can have 40 real postures, Adv. Robot Kinemat.: Anal. Control, 1-10 (1998) · Zbl 0953.70006
[13] Emiris, I. Z.; Moroz, G., The assembly modes of rigid 11-bar linkages, (IFToMM 2011 World Congress. IFToMM 2011 World Congress, Jun 2011, Guanajuato, Mexico (2011))
[14] Emiris, I. Z.; Mourrain, B., Computer algebra methods for studying and computing molecular conformations, Algorithmica, 25, 372-402 (1999)
[15] Emiris, I.; Tsigaridas, E.; Varvitsiotis, A., Mixed volume and distance geometry techniques for counting Euclidean embeddings of rigid graphs, (Mucherino, A.; Lavor, C.; Liberti, L.; Maculan, N., Distance Geometry: Theory, Methods and Applications (2013)), 23-45 · Zbl 1269.05077
[16] Emmerich, D., Structures Tendues et Autotendantes. Ecole d’Architecture de Paris la Villette (1988)
[17] Faugère, J.; Lazard, D., The combinatorial classes of parallel manipulators, Mech. Mach. Theory, 30, 6, 765-776 (1995)
[18] Gortler, S.; Healy, A.; Thurston, D., Characterizing generic global rigidity, Am. J. Math., 132, 4, 897-939 (2010) · Zbl 1202.52020
[19] Grasegger, G.; Koutschan, C.; Tsigaridas, E., Lower bounds on the number of realizations of rigid graphs, Exp. Math., 1-12 (2018)
[20] Hunter, J. D., Matplotlib: a 2D graphics environment, Comput. Sci. Eng., 9, 3, 90-95 (2007)
[21] Jackson, B.; Owen, J., Equivalent realisations of rigid graphs, (10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (2017)), 283-289
[22] Jackson, B.; Owen, J., Equivalent realisations of a rigid graph, Discrete Appl. Math., 256, 45-58 (2019) · Zbl 1405.05037
[23] Laman, G., On graphs and rigidity of plane skeletal structures, J. Eng. Math., 4, 4, 331-340 (Oct 1970), URL
[24] Liberti, L.; Masson, B.; Lee, J.; Lavor, C.; Mucherino, A., On the number of realizations of certain Henneberg graphs arising in protein conformation, Discrete Appl. Math., 165, 213-232 (2014) · Zbl 1288.05121
[25] Maxwell, J., On the calculation of the equilibrium and stiffness of frames, Philos. Mag., 39, 12 (1864)
[26] Pedregosa, F.; Varoquaux, G.; Gramfort, A.; Michel, V.; Thirion, B.; Grisel, O.; Blondel, M.; Prettenhofer, P.; Weiss, R.; Dubourg, V.; Vanderplas, J.; Passos, A.; Cournapeau, D.; Brucher, M.; Perrot, M.; Duchesnay, E., Scikit-learn: machine learning in Python, J. Mach. Learn. Res., 12, 2825-2830 (2011) · Zbl 1280.68189
[27] Pollaczek-Geiringer, H., Über die Gliederung ebener Fachwerke, Z. Angew. Math. Mech. (ZAMM), 7, 1, 58-72 (1927) · JFM 53.0743.02
[28] Pollaczek-Geiringer, H., Zur Gliederungstheorie Räumlicher Fachwerke, Z. Angew. Math. Mech. (ZAMM), 12, 6, 369-376 (1932) · JFM 58.1265.09
[29] Schulze, B.; Whiteley, W., Rigidity and scene analysis, (CRC Press LLC, vol. 61 (2017)), 1593-1632
[30] Sottile, F., Enumerative real algebraic geometry, (Algorithmic and Quantitative Real Algebraic Geometry. Algorithmic and Quantitative Real Algebraic Geometry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 60 (2003), AMS), 139-180 · Zbl 1081.14080
[31] Steffens, R.; Theobald, T., Mixed volume techniques for embeddings of Laman graphs, Comput. Geom., 43, 84-93 (2010) · Zbl 1225.05186
[32] Tay, T.-S.; Whiteley, W., Generating isostatic frameworks, Topol. Struct., 21-69 (1985) · Zbl 0574.51025
[33] Verschelde, J., Modernizing PHCpack through phcpy, (Proceedings of the 6th European Conference on Python in Science. Proceedings of the 6th European Conference on Python in Science, EuroSciPy 2013 (2014)), 71-76
[34] Walter, D.; Husty, M. L., On a 9-bar linkage, its possible configurations and conditions for paradoxical mobility, (IFToMM World Congress. IFToMM World Congress, Besançon, France (2007))
[35] Whiteley, W., Cones, infinity and one-story buildings, Topol. Struct., 8, 53-70 (1983) · Zbl 0545.51017
[36] Zelazo, D.; Franchi, A.; Allgöwer, F.; Bülthoff, H. H.; Giordano, P., Rigidity maintenance control for multi-robot systems, (Robotics: Science and Systems. Robotics: Science and Systems, Sydney, Australia (2012))
[37] Zhu, Z.; So, A.-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.