On the maximal number of real embeddings of minimally rigid graphs in R^2,R^3 and S^2

DOI10.1016/J.JSC.2019.10.015MaRDI QIDQ2200306zbMATH OpenOpenAlexFDO

Authors Evangelos Bartzos, Ioannis Z. Emiris, Jan Legerský, Elias P. Tsigaridas

Publication date 19 September 2020

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.12800

zbMATH Keywords

Cayley-Menger matrixcoupler curveLaman graphmixed volumereal boundrigid graph

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: Rigidity theory studies the properties of graphs that can have rigid embeddings in a euclidean space $mathbb{R}^d$ or on a sphere and 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 the proceedings of ISSAC 2018 (Bartzos et al, 2018).

Recommendations

• On the maximal number of real embeddings of spatial minimally rigid graphs
• New upper bounds for the number of embeddings of minimally rigid graphs
• On the number of embeddings of minimally rigid graphs
• Algebraic methods for counting Euclidean embeddings of rigid graphs
• On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs

Cites work

• A Polyhedral Method for Sparse Systems with Many Positive Solutions
• Characterizing generic global rigidity
• Equivalent realisations of a rigid graph
• Generic global rigidity
• scientific article; zbMATH DE number 3868113 (Why is no real title available?)
• scientific article; zbMATH DE number 3917126 (Why is no real title available?)
• scientific article; zbMATH DE number 1304541 (Why is no real title available?)
• scientific article; zbMATH DE number 1984328 (Why is no real title available?)
• scientific article; zbMATH DE number 5245178 (Why is no real title available?)
• scientific article; zbMATH DE number 3331438 (Why is no real title available?)
• Mixed volume and distance geometry techniques for counting Euclidean embeddings of rigid graphs
• Mixed volume techniques for embeddings of Laman graphs
• On graphs and rigidity of plane skeletal structures
• On the maximal number of real embeddings of spatial minimally rigid graphs
• On the number of realizations of certain Henneberg graphs arising in protein conformation
• Scikit-learn: machine learning in Python
• The number of embeddings of minimally rigid graphs
• The number of realizations of a Laman graph
• The number of roots of a system of equations
• Universal Rigidity and Edge Sparsification for Sensor Network Localization

Cited in

(13)

• The number of embeddings of minimally rigid graphs
• On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs
• An asymptotic upper bound for graph embeddings
• New upper bounds for the number of embeddings of minimally rigid graphs
• Counting realizations of Laman graphs on the sphere
• On the maximal number of real embeddings of spatial minimally rigid graphs
• Coupler curves of moving graphs and counting realizations of rigid graphs
• Computing Circuit Polynomials in the Algebraic Rigidity Matroid
• The number of realisations of a rigid graph in Euclidean and spherical geometries
• Shape stabilization and flocking control for multi-agent systems with infinitesimal ratio-of-distance rigidity
• Combinatorial resultants in the algebraic rigidity matroid
• Irreducible components of sets of points in the plane that satisfy distance conditions
• The m-Bézout bound and distance geometry

Describes a project that uses

Uses Software

• Scikit
• phcpy
• LamanGraphs
• PHCpack
• Matplotlib

This page was built for publication: On the maximal number of real embeddings of minimally rigid graphs in \(\mathbb{R}^2,\mathbb{R}^3\) and \(S^2\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2200306)