Augmenting the rigidity of a graph in \(\mathbb R^{2}\)

DOI10.1007/s00453-009-9300-9zbMath1213.68449MaRDI QIDQ627536

Alfredo Daniel Garcia, F. Javier Tejel

Publication date: 2 March 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9300-9

zbMATH Keywords

NP-completeness; rigid graph; augmenting problem; Laman graph

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C42: Density (toughness, etc.)

Related Items

Characterizing redundant rigidity and redundant global rigidity of body-hinge graphs

Cites Work

• Operations on rigid formations of autonomous agents
• Source location with rigidity and tree packing requirements
• Edge-connectivity augmentation problems
• Connectivity augmentation of networks: Structures and algorithms. Papers from the workshop held at Eötvös University, Budapest, Hungary, November 1994
• An algorithm for two-dimensional rigidity percolation: The pebble game
• A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid.
• Incrementing bipartite digraph edge-connectivity
• Planar minimally rigid graphs and pseudo-triangulations
• Connected rigidity matroids and unique realizations of graphs
• A smallest augmentation to 3-connect a graph
• On graphs and rigidity of plane skeletal structures
• Rigid realizations of graphs on small grids
• Birigidity in the Plane
• On Some Problems in the Design of Plane Skeletal Structures
• Conditions for Unique Graph Realizations
• Augmentation Problems
• Edge-Connectivity Augmentation with Partition Constraints
• An efficient algorithm for testing the generic rigidity of graphs in the plane
• Augmenting Outerplanar Graphs
• Algorithms – ESA 2004
• Acute triangulations of polygons
• Algorithms - ESA 2003
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item