Lower bounds on the number of realizations of rigid graphs

DOI10.1080/10586458.2018.1437851zbMATH Open1442.05044arXiv1710.08237OpenAlexW3101761638WikidataQ97524448 ScholiaQ97524448MaRDI QIDQ5114449FDOQ5114449

Christoph Koutschan, Elias P. Tsigaridas, Georg Grasegger

Publication date: 23 June 2020

Published in: Experimental Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• FGb: A Library for Computing Gröbner Bases
• On graphs and rigidity of plane skeletal structures
• Title not available (Why is that?)
• Title not available (Why is that?)
• Molecular distance geometry methods: from continuous to discrete
• 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
• Mixed volume techniques for embeddings of Laman graphs
• Equivalent realisations of a rigid graph
• Mixed Volume and Distance Geometry Techniques for Counting Euclidean Embeddings of Rigid Graphs
• Computing the number of realizations of a Laman graph
• Algebraic methods for counting Euclidean embeddings of rigid graphs
• On spaces of infinitesimal motions and three dimensional Henneberg extensions

Cited In (11)

• 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
• Title not available (Why is that?)
• Counting realizations of Laman graphs on the sphere
• Coupler curves of moving graphs and counting realizations of rigid graphs
• 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
• On rigidity and realizability of weighted graphs

Uses Software

• FGb
• LamanGraphs

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)