On the maximal number of real embeddings of minimally rigid graphs in , and S2
Introduction
Rigidity theory is a very wide area of mathematical research that combines elements of graph theory and algebraic geometry. The numerous applications of rigid graphs in other domains, such as robotics (Faugère and Lazard, 1995; Walter and Husty, 2007; Zelazo et al., 2012), structural bioinformatics (Emiris and Mourrain, 1999; Liberti et al., 2014), sensor network localization (Zhu et al., 2010) and architecture (Emmerich, 1988), give additional motivation to find efficient algorithms to compute them and classify their properties. One of the open problems in rigidity theory is to determine bounds on the maximal number of real embeddings of rigid graphs. We are interested in improving the currently known bounds.
An embedding of a simple graph in a euclidean space is a map from the set V to . We require that it satisfies certain edge constraints, namely, the distance between the images of any two adjacent vertices equals a given edge length. Let be a configuration of points in and be the vector of edge lengths induced by p. The graph G with edge lengths λ is called rigid in if the number of embeddings in having the same edge lengths is finite modulo rigid motions. The graph G is generically rigid in iff it is rigid in for edge lengths induced by any generic configuration. Additionally, if G is generically rigid and removing any edge yields a non-rigid graph , then G is called generically minimally rigid in .
In the first half of the 20th century, Pollaczek-Geiringer, 1927, Pollaczek-Geiringer, 1932 made notable progress on understanding the properties of minimally rigid graphs, but her work was forgotten. Laman (1970) rediscovered that we can fully characterize the minimally rigid graphs in using the edge count property (Maxwell, 1864). Since then, these graphs are known as Laman graphs. In honor of Hilda Pollaczek-Geiringer, we have chosen to call minimally rigid graphs in Geiringer graphs, as in (Grasegger et al., 2018). Rigidity is defined also on spheres (Whiteley, 1983). In the case of , the edge count property of Laman graphs holds for minimally rigid graphs, while the distance from the origin poses an additional constraint.
Generically minimally rigid graphs are of great interest since they correspond to well-constrained algebraic systems. Given a rigid graph in and edge lengths , we denote by the number of embeddings of G in , which are the real solutions of the corresponding algebraic systems. Let denote the maximal number of real embeddings among all the choices of λ that yield a rigid conformation, i.e., when is finite. The total number of solutions of the corresponding algebraic system in is the number of complex embeddings of a graph. This gives a natural upper bound for and is denoted by . Finally, we write and for the maximal number of complex and real embeddings, respectively, among all n-vertex rigid graphs in . We will also use the notation , and for the real and complex number of embeddings on .
We can use lower and upper bounds on to establish lower and upper bounds on by gluing mechanisms in certain ways (Borcea and Streinu, 2004; Grasegger et al., 2018).
Previous results Asymptotic upper bounds for were computed as complex bounds of the determinantal variety of the distance matrix in (Borcea, 2002; Borcea and Streinu, 2004), while mixed volume techniques were applied in the case in (Steffens and Theobald, 2010). Both bounds behave asymptotically as , which is considered as a rather loose bound. Tighter bounds for specific classes of Laman graphs can be found in (Jackson and Owen, 2019).
Graph-specific approaches have been also used to compute bounds of graph embeddings in and . Mixed volume techniques (Emiris et al., 2013) and a recent combinatorial algorithm for Laman graphs (Capco et al., 2018) have treated the complex case. In (Borcea and Streinu, 2004), it is proven that using coupler curves and some advanced stochastic methods are applied to show that in (Emiris and Moroz, 2011). The latter yields as a lower bound on maximal number of embeddings for Laman graphs; we improve this bound. The best known lower bound for is (Emiris et al., 2013); we also improve this bound. In general, the maximal number of real embeddings both in and for graphs with vertices is known.
The main question is whether we can specify edge lengths that maximize the number of real embeddings. This question is related to more general open problems in real algebraic geometry concerning possible gaps between the number of complex and real solutions of an algebraic system depending on its parameters. In that area, there exist some upper (Sottile, 2003) and lower (Bihan et al., 2008, Bihan et al., 2018) bounds on the number of real positive roots, which take advantage of the structure of polynomials. Regarding applied cases, there is also the example on the maximization of the number of real Stewart-Gough Platform configurations (Dietmaier, 1998), using a gradient descent method.
Our contribution We extend the existing results on the maximal number of real embeddings of Laman and Geiringer graphs. We also provide bounds in the previously untreated case of spherical embeddings. In both cases, we have constructed all minimally rigid graphs using the methods described in (Grasegger et al., 2018) and we classify them according to the last Henneberg step. Subsequently, we use different systems to model our problem algebraically and we compute upper bounds for all computationally feasible cases. Since our main goal is to maximize the number of real embeddings, we specify the edge lengths in each case using certain heuristics.
In the ISSAC 2018 version we have treated the case of Geiringer graphs. We have developed a new method inspired by coupler curves that can search efficiently huge parametric spaces combining local and global sampling. An open-source implementation of our method under GNU GPL v3 license is available in (Bartzos and Legerský, 2018). This implementation uses the polyhedral homotopy solver PHCpack (Verschelde, 2014) to find the solutions of algebraic systems. We are not aware of any other similar method. The method gave the maximal numbers of real embeddings of all 7-vertex Geiringer graphs and improved the existing lower maximal bound from to using selected 8-vertex graphs (Bartzos et al., 2018).
Besides the results announced in ISSAC 2018, we also improve the existing lower bounds on the number of real embeddings of selected Laman graphs on the plane and sphere. In these cases, we use some standard sampling methods to find parameters that maximize the number of embeddings. Our results give the maximal numbers of real embeddings of all 6-vertex and 7-vertex Laman graphs in and respectively. We also specify parameters for larger graphs (up to 10 vertices for the embeddings on the plane and up to 8 vertices for spherical embeddings). These computations improve the existing lower bound on the maximal number of real embeddings from to for , while they establish as a lower bound for the number of embeddings in .
Organization We organize the paper as follows: in Section 2, we give a brief introduction on rigidity theory and we describe the algebraic modeling in hand. In Section 3, we present the sampling methods that we use. Here we describe the method for maximizing the number of real embeddings of Geiringer graphs that is inspired by coupler curves. It previously appeared in (Bartzos et al., 2018). In Section 4, we present our results in , , and . We derive a new lower bound on the maximal number of real embeddings for the first two cases and we restate the lower bound appeared in the proceedings of ISSAC 2018 for the spatial embeddings. In Section 5, we present an overview of our results and some future research problems.
Section snippets
Rigidity and & algebraic modeling
First, we present some standard results about minimally rigid graphs (Sec. 2.1). We subsequently introduce the algebraic formulations we use to establish upper bounds and lower bounds on the number of embeddings. In Sec. 2.2, we present a variation of the squared distance equations between adjacent vertices, while in Sec. 2.3 we apply the Cayley-Menger embeddability conditions.
Increasing the number of real embeddings
Our main goal throughout our experiments was to find the parameters that can maximize the number of real embeddings of minimally rigid graphs. One open problem in rigidity theory is whether the maximal number of real embeddings of a given graph can be the same as the number of complex embeddings. Although there exists an 8-vertex Laman graph for which it has been proven that (Jackson and Owen, 2017), in most cases we consider the number of complex embeddings as the upper bound we
Classification and lower bounds
The first step of our procedure was to construct Laman and Geiringer graphs by Henneberg steps. We subsequently removed isomorphic duplicates and classified them according to the last Henneberg move as described in Section 2.1. Following an idea explained in (Grasegger et al., 2018), we represented every graph isomorphism class with an integer and we proceeded using a SageMath implementation.
A first upper bound on the number of embeddings is the mixed volume of systems of sphere and distance
Conclusion and future work
In this paper we have developed and used efficient methods to maximize the number of real embeddings of rigid graphs in the case of planar, spherical and spatial embeddings. We have introduced a new technique for Geiringer graphs, that exploits an invariance property of coupler curves to select the sampling parameters at each iteration. This procedure led to classification results and to an improvement of the asymptotic lower bounds.
As future work, a first goal would be to ameliorate the
Declaration of Competing Interest
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
Acknowledgements
IZE is partially supported, EB and JL are fully supported by project ARCADES which has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 675789. ET is partially supported by ANR JCJC GALOP (ANR-17-CE40-0009) and the PGMO grant ALMA. IZE participates in team Aromath, joint between Inria Sophia-Antipolis and NKUA.
References (37)
- et al.
The combinatorial classes of parallel manipulators
Mech. Mach. Theory
(1995) - et al.
On the number of realizations of certain Henneberg graphs arising in protein conformation
Discrete Appl. Math.
(2014) - et al.
Mixed volume techniques for embeddings of Laman graphs
Comput. Geom.
(2010) - et al.
On the maximal number of real embeddings of spatial minimally rigid graphs
- et al.
Graph embeddings in the plane, space and sphere — source code and results
The number of roots of a system of equations
Funct. Anal. Appl.
(1975)- et al.
On the sharpness of fewnomial bounds and the number of components of fewnomial hypersurfaces
- et al.
A polyhedral method for sparse systems with many positive solutions
Theory and Applications of Distance Geometry
(1970)Point configurations and Cayley-Menger varieties
The number of embeddings of minimally rigid graphs
Discrete Comput. Geom.
The number of realizations of a Laman graph
SIAM J. Appl. Algebra Geom.
Generic global rigidity
Discrete Comput. Geom.
Convex Optimization & Euclidean Distance Geometry
The Stewart-Gough platform of general geometry can have 40 real postures
Adv. Robot Kinemat.: Anal. Control
The assembly modes of rigid 11-bar linkages
Computer algebra methods for studying and computing molecular conformations
Algorithmica
Mixed volume and distance geometry techniques for counting Euclidean embeddings of rigid graphs
Cited by (15)
An asymptotic upper bound for graph embeddings
2023, Discrete Applied MathematicsCOUPLER CURVES OF MOVING GRAPHS AND COUNTING REALIZATIONS OF RIGID GRAPHS
2024, Mathematics of ComputationComputing Circuit Polynomials in the Algebraic Rigidity Matroid
2023, SIAM Journal on Applied Algebra and GeometryNew Upper Bounds for the Number of Embeddings of Minimally Rigid Graphs
2022, Discrete and Computational Geometry