Combinatorial pseudo-triangulations

DOI10.1016/J.DISC.2005.09.045zbMATH Open1109.05037arXivmath/0307370OpenAlexW2089708856MaRDI QIDQ864146FDOQ864146

Authors: David Orden, Brigitte Servatius, Herman J. Servatius, Francisco Santos 

Publication date: 13 February 2007

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We prove that a planar graph is generically rigid in the plane if and only if it can be embedded as a pseudo-triangulation. This generalizes the main result of math.CO/0307347 which treats the minimally generically rigid case. The proof uses the concept of combinatorial pseudo-triangulation, CPT, in the plane and has two main steps: showing that a certain ``generalized Laman property is a necessary and sufficient condition for a CPT to be ``stretchable, and showing that all generically rigid plane graphs admit a CPT assignment with that property. Additionally, we propose the study of combinatorial pseudo-triangulations on closed surfaces.

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

Recommendations

• Planar minimally rigid graphs and pseudo-triangulations
• Enumerating pseudo-triangulations in the plane
• Planar minimally rigid graphs and pseudo-triangulations
• Pseudo-triangulations -- a survey
• Algorithms – ESA 2004

zbMATH Keywords

rigidityplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• On graphs and rigidity of plane skeletal structures
• Title not available (Why is that?)
• Title not available (Why is that?)
• Planar minimally rigid graphs and pseudo-triangulations
• Topologically sweeping visibility complexes via pseudotriangulations
• Construction of Self-Dual Graphs
• Ray shooting in polygons using geodesic triangulations
• Title not available (Why is that?)
• The polytope of non-crossing graphs on a planar point set
• Non-crossing frameworks with non-crossing reciprocals

Cited In (11)

• 3-colorability of pseudo-triangulations
• Planar minimally rigid graphs and pseudo-triangulations
• Recognizing planar Laman graphs
• The polytope of non-crossing graphs on a planar point set
• Planar minimally rigid graphs and pseudo-triangulations
• Enumerating pseudo-triangulations in the plane
• On the number of pseudo-triangulations of certain point sets
• Matching edges and faces in polygonal partitions
• Flips in combinatorial pointed pseudo-triangulations with face degree at most four
• A vertex-face assignment for plane graphs
• Pseudo-triangulations -- a survey

This page was built for publication: Combinatorial pseudo-triangulations

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