New upper bounds for the number of embeddings of minimally rigid graphs

DOI10.1007/S00454-022-00370-3MaRDI QIDQ2172653zbMATH OpenOpenAlexFDO

Authors Evangelos Bartzos, Ioannis Z. Emiris, Raimundas Vidunas

Publication date 16 September 2022

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

distance geometryLaman graphminimally rigid graphoriented graphrigid embeddingupper bound

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Enumerative problems (combinatorial problems) in algebraic geometry (14N10) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Abstract: By definition, a rigid graph in $mathbb{R}^d$ (or on a sphere) has a finite number of embeddings up to rigid motions for a given set of edge length constraints. These embeddings are related to the real solutions of an algebraic system. Naturally, the complex solutions of such systems extend the notion of rigidity to $mathbb{C}^d$. A major open problem has been to obtain tight upper bounds on the number of embeddings in $mathbb{C}^d$, for a given number $|V|$ of vertices, which obviously also bound their number in $mathbb{R}^d$. Moreover, in most known cases, the maximal numbers of embeddings in $mathbb{C}^d$ and $mathbb{R}^d$ coincide. For decades, only the trivial bound of $O(2^{dcdot|V|})$ was known on the number of embeddings.Recently, matrix permanent bounds have led to a small improvement for $dgeq5$. This work improves upon the existing upper bounds for the number of embeddings in $mathbb{R}^d$ and $S^d$, by exploiting outdegree-constrained orientations on a graphical construction, where the proof iteratively eliminates vertices or vertex paths. For the most important cases of $d=2$ and $d=3$, the new bounds are $O(3.7764^{|V|})$ and $O(6.8399^{|V|})$, respectively. In general, the recent asymptotic bound mentioned above is improved by a factor of $1/sqrt2$. Besides being the first substantial improvement upon a long-standing upper bound, our method is essentially the first general approach relying on combinatorial arguments rather than algebraic root counts.

Recommendations

• An asymptotic upper bound for graph embeddings
• On the multihomogeneous Bézout bound on 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 maximal number of real embeddings of spatial minimally rigid graphs

Cites work

• Algorithms for graph rigidity and scene analysis
• Assigned and unassigned distance geometry: applications to biological molecules and nanostructures
• Basic Algebraic Geometry 2
• Counting realizations of Laman graphs on the sphere
• Directed graphs, decompositions, and spatial linkages
• Equivalent realisations of a rigid graph
• Graphs, networks and algorithms. Based on the translation of the 3rd German edition by Tilla Schade in collaboration with the author
• 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 3458807 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• scientific article; zbMATH DE number 3331438 (Why is no real title available?)
• Lower bounds on the number of realizations of rigid graphs
• Mixed volume and distance geometry techniques for counting Euclidean embeddings of rigid graphs
• Mixed volume techniques for embeddings of Laman graphs
• Newton polyhedra and the genus of complete intersections
• On graphs and rigidity of plane skeletal structures
• On symmetric and skew-symmetric determinantal varieties
• On the maximal number of real embeddings of minimally rigid graphs in \(\mathbb{R}^2,\mathbb{R}^3\) and \(S^2\)
• On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs
• On the number of planar orientations with prescribed degrees
• Polyedres de Newton et nombres de Milnor
• Sparse hypergraphs and pebble game algorithms
• Stabilisation of infinitesimally rigid formations of multi-robot networks
• The m-Bézout bound and distance geometry
• 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
• The Rigidity of Graphs
• Universal Rigidity and Edge Sparsification for Sensor Network Localization
• Upper bounds for permanents of $\left( {0,\,1} \right)$-matrices

Cited in

(14)

• A minmax relationship between embeddable and rigid graphs
• 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
• On the maximal number of real embeddings of minimally rigid graphs in \(\mathbb{R}^2,\mathbb{R}^3\) and \(S^2\)
• Mixed volume and distance geometry techniques for counting Euclidean embeddings of rigid graphs
• Algebraic methods for counting Euclidean embeddings of rigid graphs
• scientific article; zbMATH DE number 3920492 (Why is no real title available?)
• On the number of embeddings of minimally rigid graphs
• Lower bounds on the number of realizations of rigid graphs
• On the maximal number of real embeddings of spatial minimally rigid graphs
• Coupler curves of moving graphs and counting realizations of rigid graphs
• The number of realisations of a rigid graph in Euclidean and spherical geometries
• Irreducible components of sets of points in the plane that satisfy distance conditions

Describes a project that uses

Uses Software

• LamanGraphs
• Bezout

This page was built for publication: New upper bounds for the number of embeddings of minimally rigid graphs

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