On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs

DOI10.1007/s00200-020-00447-7zbMath1464.05266arXiv2005.14485OpenAlexW3043945154MaRDI QIDQ2025442

Evangelos Bartzos, Josef Schicho, Ioannis Z. Emiris

Publication date: 14 May 2021

Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

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

zbMATH Keywords

mixed volumepermanentcombinatorial algorithmrigid graphLaman graphBernstein's second theoremmultihomogeneous Bézout bound

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) 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 (5)

The m-Bézout bound and distance geometry ⋮ New upper bounds for the number of embeddings of minimally rigid graphs ⋮ Coupler curves of moving graphs and counting realizations of rigid graphs ⋮ Bezout ⋮ An asymptotic upper bound for graph embeddings

Uses Software

• PHCpack
• MULTIRES
• phcpy
• MonodromySolver
• LamanGraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• LamanGraphs
• Assigned and unassigned distance geometry: applications to biological molecules and nanostructures
• Bounds on the number of Eulerian orientations
• On symmetric and skew-symmetric determinantal varieties
• On the number of planar orientations with prescribed degrees
• Mixed volume techniques for embeddings of Laman graphs
• 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
• Multihomogeneous resultant formulae by means of complexes
• 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\)
• On Graver's conjecture concerning the rigidity problem of graphs
• Pebble game algorithms and sparse graphs
• On graphs and rigidity of plane skeletal structures
• Computing minimal multi-homogeneous Bezout numbers is hard
• Mixed Volume and Distance Geometry Techniques for Counting Euclidean Embeddings of Rigid Graphs
• Universal Rigidity and Edge Sparsification for Sensor Network Localization
• A Remark on Stirling's Formula
• Root counts of semi-mixed systems, and an application to counting nash equilibria
• Infinitesimally Rigid Polyhedra. I. Statics of Frameworks
• Lectures on Polytopes
• On the number of embeddings of minimally rigid graphs
• The Number of Realizations of a Laman Graph
• Using Algebraic Geometry
• Lower Bounds on the Number of Realizations of Rigid Graphs
• A Characterization of Generically Rigid Frameworks on Surfaces of Revolution
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• Upper bounds for permanents of $\left( {0,\,1} \right)$-matrices
• Solving polynomial systems via homotopy continuation and monodromy
• Multihomogeneous resultant formulae for systems with scaled support

This page was built for publication: On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs