Lower bounds on the number of realizations of rigid graphs

DOI10.1080/10586458.2018.1437851MaRDI QIDQ5114449zbMATH OpenOpenAlexWikidataFDO

Authors Georg Grasegger, Christoph Koutschan, Elias P. Tsigaridas

Publication date 23 June 2020

Published in Experimental Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

graph realizationLaman graphminimally rigid graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Symbolic computation and algebraic computation (68W30) Planar graphs; geometric and topological aspects of graph theory (05C10) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Abstract: Computing the number of realizations of a minimally rigid graph is a notoriously difficult problem. Towards this goal, for graphs that are minimally rigid in the plane, we take advantage of a recently published algorithm, which is the fastest available method, although its complexity is still exponential. Combining computational results with the theory of constructing new rigid graphs by gluing, we give a new lower bound on the maximal possible number of (complex) realizations for graphs with a given number of vertices. We extend these ideas to rigid graphs in three dimensions and we derive similar lower bounds, by exploiting data from extensive Gr"obner basis computations.

Recommendations

• On the maximal number of real embeddings of spatial minimally rigid graphs
• Algebraic methods for counting Euclidean embeddings of rigid graphs
• New upper bounds for the number of embeddings of minimally rigid graphs
• Mixed volume and distance geometry techniques for counting Euclidean embeddings of rigid graphs
• On the number of embeddings of minimally rigid graphs

Cites work

• scientific article; zbMATH DE number 3917126 (Why is no real title available?)
• scientific article; zbMATH DE number 501471 (Why is no real title available?)
• Algebraic methods for counting Euclidean embeddings of rigid graphs
• Computing the number of realizations of a Laman graph
• Equivalent realisations of a rigid graph
• FGb: A Library for Computing Gröbner Bases
• Mixed volume and distance geometry techniques for counting Euclidean embeddings of rigid graphs
• Mixed volume techniques for embeddings of Laman graphs
• Molecular distance geometry methods: from continuous to discrete
• On graphs and rigidity of plane skeletal structures
• On spaces of infinitesimal motions and three dimensional Henneberg extensions
• On the number of realizations of certain Henneberg graphs arising in protein conformation
• The number of embeddings of minimally rigid graphs
• Universal Rigidity and Edge Sparsification for Sensor Network Localization

Cited in

(14)

• On rigidity and realizability of weighted graphs
• New upper bounds for the number of embeddings of minimally rigid graphs
• The number of embeddings of minimally rigid graphs
• On the number of realizations of certain Henneberg graphs arising in protein conformation
• Equivalent realisations of a rigid graph
• scientific article; zbMATH DE number 4075121 (Why is no real title available?)
• Counting realizations of Laman graphs on the sphere
• Coupler curves of moving graphs and counting realizations of rigid graphs
• Rigid realizations of graphs with few locations in the plane
• Computing the number of realizations of a Laman graph
• Realizations of rigid graphs
• The number of realisations of a rigid graph in Euclidean and spherical geometries
• On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs
• Generic rigidity of molecular graphs via ear decomposition

Describes a project that uses

Uses Software

• LamanGraphs
• FGb

This page was built for publication: Lower bounds on the number of realizations of rigid graphs

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