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

DOI10.1007/s00454-022-00370-3zbMath1497.05180arXiv2010.10578OpenAlexW3093733732MaRDI QIDQ2172653

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

upper bounddistance geometryoriented graphLaman graphminimally rigid graphrigid embedding

Mathematics Subject Classification ID

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

Related Items (2)

Coupler curves of moving graphs and counting realizations of rigid graphs ⋮ An asymptotic upper bound for graph embeddings

Uses Software

• Bezout
• LamanGraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Assigned and unassigned distance geometry: applications to biological molecules and nanostructures
• On symmetric and skew-symmetric determinantal varieties
• The m-Bézout bound and distance geometry
• On the number of planar orientations with prescribed degrees
• Mixed volume techniques for embeddings of Laman graphs
• Sparse hypergraphs and pebble game algorithms
• The number of roots of a system of equations
• Polyedres de Newton et nombres de Milnor
• Newton polyhedra and the genus of complete intersections
• Equivalent realisations of a rigid graph
• The number of embeddings of minimally rigid graphs
• Graphs, networks and algorithms. Based on the translation of the 3rd German edition by Tilla Schade in collaboration with the author
• On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs
• Counting realizations of Laman graphs on the sphere
• On the maximal number of real embeddings of minimally rigid graphs in \(\mathbb{R}^2,\mathbb{R}^3\) and \(S^2\)
• Directed graphs, decompositions, and spatial linkages
• On graphs and rigidity of plane skeletal structures
• Mixed Volume and Distance Geometry Techniques for Counting Euclidean Embeddings of Rigid Graphs
• Universal Rigidity and Edge Sparsification for Sensor Network Localization
• The Rigidity of Graphs
• The Number of Realizations of a Laman Graph
• Basic Algebraic Geometry 2
• Lower Bounds on the Number of Realizations of Rigid Graphs
• Stabilisation of infinitesimally rigid formations of multi-robot networks
• Upper bounds for permanents of $\left( {0,\,1} \right)$-matrices
• Algorithms - ESA 2003

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