Enumerating constrained non-crossing minimally rigid frameworks

DOI10.1007/S00454-007-9026-XMaRDI QIDQ946684zbMATH OpenOpenAlexFDO

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

Publication date 24 September 2008

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

rigidityconstrained Delaunay triangulationconstrained non-crossing minimally rigid frameworksgeometric enumeration

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Abstract: In this paper we present an algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-and-joint frameworks under edge constraints (also called constrained non-crossing Laman frameworks) on a given generic set of $n$ points. Our algorithm is based on the reverse search paradigm of Avis and Fukuda. It generates each output graph in $O(n^4)$ time and O(n) space, or, slightly different implementation, in $O(n^3)$ time and $O(n^2)$ space. In particular, we obtain that the set of all the constrained non-crossing Laman frameworks on a given point set is connected by flips which restore the Laman property.

Recommendations

• Enumerating non-crossing minimally rigid frameworks
• Enumerating Non-crossing Minimally Rigid Frameworks
• Fast enumeration algorithms for non-crossing geometric graphs
• Enumerating Constrained Non-crossing Geometric Spanning Trees
• Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees

Cites work

• 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 822231 (Why is no real title available?)
• scientific article; zbMATH DE number 863478 (Why is no real title available?)
• scientific article; zbMATH DE number 963168 (Why is no real title available?)
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• Acute triangulations of polygons
• Algorithms for graph rigidity and scene analysis
• An algorithm for two-dimensional rigidity percolation: The pebble game
• Enumerating non-crossing minimally rigid frameworks
• Enumerating pseudo-triangulations in the plane
• Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time
• Gray code enumeration of plane straight-line graphs
• On graphs and rigidity of plane skeletal structures
• Pebble game algorithms and \((k,l)\)-sparse graphs
• Reverse search for enumeration
• The complexity of detecting crossingfree configurations in the plane

Cited in

(9)

• Combinatorial Algorithm for a Lower Bound on Frame Rigidity
• Enumerating non-crossing minimally rigid frameworks
• Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees
• Enumerating Non-crossing Minimally Rigid Frameworks
• Enumerating combinatorial resultant trees
• Non-crossing frameworks with non-crossing reciprocals
• Fast enumeration algorithms for non-crossing geometric graphs
• Improving upper and lower bounds for the total number of edge crossings of Euclidean minimum weight Laman graphs
• An inductive construction of minimally rigid body-hinge simple graphs

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

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