The number of realizations of a Laman graph

DOI10.1137/17M1118312zbMATH Open1439.14182arXiv1701.05500WikidataQ130159433 ScholiaQ130159433MaRDI QIDQ4564015FDOQ4564015

Authors: Jose Capco, Matteo Gallet, Georg Grasegger, Christoph Koutschan, Niels Lubbes, Josef Schicho 

Publication date: 12 June 2018

Published in: SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

Abstract: Laman graphs model planar frameworks that are rigid for a general choice of distances between the vertices. There are finitely many ways, up to isometries, to realize a Laman graph in the plane. Such realizations can be seen as solutions of systems of quadratic equations prescribing the distances between pairs of points. Using ideas from algebraic and tropical geometry, we provide a recursive formula for the number of complex solutions of such systems.

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

Recommendations

• Computing the number of realizations of a Laman graph
• Counting realizations of Laman graphs on the sphere
• On the number of embeddings of minimally rigid graphs
• Mixed volume techniques for embeddings of Laman graphs
• Equivalent realisations of a rigid graph

zbMATH Keywords

graph embeddingtropical geometryPuiseux seriesgraph realizationEuclidean embeddingLaman graphminimally rigid graph

Mathematics Subject Classification ID

Combinatorial aspects of tropical varieties (14T15) Graph theory (05C99) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25) Projective and enumerative algebraic geometry (14N99)

Cites Work

• FGb: A Library for Computing Gröbner Bases
• The On-Line Encyclopedia of Integer Sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• An algorithm for two-dimensional rigidity percolation: The pebble game
• On graphs and rigidity of plane skeletal structures
• Characterizing generic global rigidity
• Geometric Fundamentals of Robotics
• Enumerative tropical algebraic geometry in ℝ²
• On Generic Rigidity in the Plane
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Certifying and constructing minimally rigid graphs in the plane
• A tropical toolkit
• Fibers of tropicalization
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the number of realizations of certain Henneberg graphs arising in protein conformation
• The number of embeddings of minimally rigid graphs
• A network theory approach to the rigidity of skeletal structures. II: Laman's theorem and topological formulae
• 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
• Frameworks with crystallographic symmetry
• Configurations of lines in space and combinatorial rigidity
• Computing the number of realizations of a Laman graph
• Algebraic methods for counting Euclidean embeddings of rigid graphs
• Title not available (Why is that?)
• Towards an optimal algorithm for recognizing Laman graphs

Cited In (24)

• An asymptotic upper bound for graph embeddings
• Mixed volume techniques for embeddings of Laman graphs
• Graphs with flexible labelings allowing injective realizations
• Computing Circuit Polynomials in the Algebraic Rigidity Matroid
• New upper bounds for the number of embeddings of minimally rigid graphs
• Equivalent realisations of a rigid graph
• Title not available (Why is that?)
• The algebraic matroid of the finite unit norm tight frame (funtf) variety
• On the maximal number of real embeddings of minimally rigid graphs in \(\mathbb{R}^2,\mathbb{R}^3\) and \(S^2\)
• Counting realizations of Laman graphs on the sphere
• The Tropical Cayley--Menger Variety
• Globally rigid graphs are fully reconstructible
• The non-solvability by radicals of generic 3-connected planar Laman graphs
• Coupler curves of moving graphs and counting realizations of rigid graphs
• Generic symmetry-forced infinitesimal rigidity: translations and rotations
• Combinatorial and geometric properties of planar Laman graphs
• LamanGraphs
• Realizations of rigid graphs
• Computing the number of realizations of a Laman graph
• Vertex spanning planar Laman graphs in triangulated surfaces
• 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
• FlexRiLoG -- a SageMath package for motions of graphs
• And yet it moves: paradoxically moving linkages in kinematics

Uses Software

• FGb
• OEIS

This page was built for publication: The number of realizations of a Laman graph

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