Enumerating non-crossing minimally rigid frameworks

DOI10.1007/s00373-007-0709-0zbMath1123.68084OpenAlexW2069126428MaRDI QIDQ2373440

Shin-ichi Tanigawa, Ileana Streinu, Makoto Ohsaki, 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

Exact enumeration problems, generating functions (05A15) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) 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)

Related Items (4)

Amortized efficiency of generating planar paths in convex position ⋮ Fast enumeration algorithms for non-crossing geometric graphs ⋮ Enumerating constrained non-crossing minimally rigid frameworks ⋮ Flips in planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• An algorithm for two-dimensional rigidity percolation: The pebble game
• Enumerating pseudo-triangulations in the plane
• An efficient algorithm for enumeration of triangulations
• Reverse search for enumeration
• On graphs and rigidity of plane skeletal structures
• Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm
• Acute triangulations of polygons
• Algorithms - ESA 2003
• Algorithms and Data Structures
• Enumerating triangulation paths

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