Enumerating non-crossing minimally rigid frameworks

DOI10.1007/S00373-007-0709-0MaRDI QIDQ2373440zbMATH OpenOpenAlexFDO

Authors M. Ohsaki, Ileana Streinu, Shin-Ichi Tanigawa, David Avis, Naoki Katoh

Publication date 19 July 2007

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00373-007-0709-0

zbMATH Keywords

RigidityGeometric enumerationMinimally rigid graphNon-crossing minimally rigid frameworks

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Exact enumeration problems, generating functions (05A15) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Recommendations

• Enumerating Non-crossing Minimally Rigid Frameworks
• Enumerating constrained non-crossing minimally rigid frameworks
• Combinatorial rigidity of symmetric and periodic frameworks
• Generic combinatorial rigidity of periodic frameworks
• The number of embeddings of minimally rigid graphs
• On the number of embeddings of minimally rigid graphs
• Combinatorial Algorithm for a Lower Bound on Frame Rigidity
• <scp>Almost‐Rigidity</scp> of Frameworks
• Maximal rigid objects as noncrossing bipartite graphs
• Combinatorial rigidity. Graphs and matroids in the theory of rigid frameworks

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?)
• scientific article; zbMATH DE number 2038815 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 2209740 (Why is no real title available?)
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• Acute triangulations of polygons
• Algorithms and Data Structures
• Algorithms for graph rigidity and scene analysis
• An algorithm for two-dimensional rigidity percolation: The pebble game
• An efficient algorithm for enumeration of triangulations
• Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm
• Enumerating pseudo-triangulations in the plane
• Enumerating triangulation paths
• On graphs and rigidity of plane skeletal structures
• Pebble game algorithms and \((k,l)\)-sparse graphs
• Reverse search for enumeration
• Structural mechanics: Graph and matrix methods.

Cited in

(6)

• Non-crossing frameworks with non-crossing reciprocals
• Enumerating constrained non-crossing minimally rigid frameworks
• Amortized efficiency of generating planar paths in convex position
• Fast enumeration algorithms for non-crossing geometric graphs
• Enumerating Non-crossing Minimally Rigid Frameworks
• Flips in planar graphs

This page was built for publication: Enumerating non-crossing minimally rigid frameworks

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