The number of realizations of a Laman graph

DOI10.1137/17M1118312MaRDI QIDQ4564015zbMATH OpenWikidataFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 5080025 (Why is no real title available?)
• scientific article; zbMATH DE number 1304541 (Why is no real title available?)
• scientific article; zbMATH DE number 480232 (Why is no real title available?)
• scientific article; zbMATH DE number 501471 (Why is no real title available?)
• scientific article; zbMATH DE number 1827070 (Why is no real title available?)
• scientific article; zbMATH DE number 1908322 (Why is no real title available?)
• scientific article; zbMATH DE number 786605 (Why is no real title available?)
• scientific article; zbMATH DE number 6437647 (Why is no real title available?)
• A network theory approach to the rigidity of skeletal structures. II: Laman's theorem and topological formulae
• A tropical toolkit
• Algebraic methods for counting Euclidean embeddings of rigid graphs
• An algorithm for two-dimensional rigidity percolation: The pebble game
• Certifying and constructing minimally rigid graphs in the plane
• Characterizing generic global rigidity
• Computing the number of realizations of a Laman graph
• Configurations of lines in space and combinatorial rigidity
• Enumerative tropical algebraic geometry in ℝ²
• Equivalent realisations of a rigid graph
• FGb: A Library for Computing Gröbner Bases
• Fibers of tropicalization
• Frameworks with crystallographic symmetry
• Geometric Fundamentals of Robotics
• Mixed volume and distance geometry techniques for counting Euclidean embeddings of rigid graphs
• Mixed volume techniques for embeddings of Laman graphs
• On Generic Rigidity in the Plane
• On graphs and rigidity of plane skeletal structures
• On the number of realizations of certain Henneberg graphs arising in protein conformation
• The On-Line Encyclopedia of Integer Sequences
• The number of embeddings of minimally rigid graphs
• Towards an optimal algorithm for recognizing Laman graphs

Cited in

(26)

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

Describes a project that uses

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)