Elsevier

Journal of Symbolic Computation

Volume 102, January–February 2021, Pages 189-208
Journal of Symbolic Computation

On the maximal number of real embeddings of minimally rigid graphs in R2, R3 and S2

https://doi.org/10.1016/j.jsc.2019.10.015Get rights and content

Abstract

Rigidity theory studies the properties of graphs that can have rigid embeddings in a euclidean space Rd 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 R3. 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 R2 and R3, while in the case of S2 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 the proceedings of ISSAC 2018 (Bartzos et al., 2018).

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 G=(V,E) in a euclidean space Rd is a map from the set V to Rd. 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 p=(p1,p2,pn) be a configuration of n=|V| points in Rd and λ=(pipj)ijE be the vector of edge lengths induced by p. The graph G with edge lengths λ is called rigid in Rd if the number of embeddings in Rd having the same edge lengths is finite modulo rigid motions. The graph G is generically rigid in Rd iff it is rigid in Rd for edge lengths induced by any generic configuration. Additionally, if G is generically rigid and removing any edge eE yields a non-rigid graph Ge, then G is called generically minimally rigid in Rd.

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 R2 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 R3 Geiringer graphs, as in (Grasegger et al., 2018). Rigidity is defined also on spheres (Whiteley, 1983). In the case of S2, 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 G=(V,E) in Rd and edge lengths λ={λij}ijER+|E|, we denote by rd(G,λ) the number of embeddings of G in Rd, which are the real solutions of the corresponding algebraic systems. Let rd(G) denote the maximal number of real embeddings among all the choices of λ that yield a rigid conformation, i.e., when rd(G,λ) is finite. The total number of solutions of the corresponding algebraic system in Cd is the number of complex embeddings of a graph. This gives a natural upper bound for rd(G) and is denoted by cd(G). Finally, we write cd(n) and rd(n) for the maximal number of complex and real embeddings, respectively, among all n-vertex rigid graphs in Cd. We will also use the notation rS2(G,λ), rS2(G) and cS2(G) for the real and complex number of embeddings on S2.

We can use lower and upper bounds on rd(G) to establish lower and upper bounds on rd(n) by gluing mechanisms in certain ways (Borcea and Streinu, 2004; Grasegger et al., 2018).

Previous results  Asymptotic upper bounds for rd(n) 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 d=2 in (Steffens and Theobald, 2010). Both bounds behave asymptotically as O(2dn), 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 R2 and R3. 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 r2(6)=24 using coupler curves and some advanced stochastic methods are applied to show that r2(7)=56 in (Emiris and Moroz, 2011). The latter yields 2.3003n as a lower bound on maximal number of embeddings for Laman graphs; we improve this bound. The best known lower bound for r3(n) is 2.51984n (Emiris et al., 2013); we also improve this bound. In general, the maximal number of real embeddings both in d=2 and d=3 for graphs with n6 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 2.51984n to 2.6390n 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 S2 and R2 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 2.3003n to 2.3811n for d=2, while they establish 2.51984n as a lower bound for the number of embeddings in S2.

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 d=2, S2, and d=3. 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 r2(G)<c2(G) (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)

  • C.S. Borcea et al.

    The number of embeddings of minimally rigid graphs

    Discrete Comput. Geom.

    (2004)
  • J. Capco et al.

    The number of realizations of a Laman graph

    SIAM J. Appl. Algebra Geom.

    (2018)
  • R. Connelly

    Generic global rigidity

    Discrete Comput. Geom.

    (2005)
  • M. Dattorro et al.

    Convex Optimization & Euclidean Distance Geometry

    (2005)
  • P. Dietmaier

    The Stewart-Gough platform of general geometry can have 40 real postures

    Adv. Robot Kinemat.: Anal. Control

    (1998)
  • I.Z. Emiris et al.

    The assembly modes of rigid 11-bar linkages

  • I.Z. Emiris et al.

    Computer algebra methods for studying and computing molecular conformations

    Algorithmica

    (1999)
  • I. Emiris et al.

    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 Mathematics
    • Computing Circuit Polynomials in the Algebraic Rigidity Matroid

      2023, SIAM Journal on Applied Algebra and Geometry
    View all citing articles on Scopus
    View full text