Planar minimally rigid graphs and pseudo-triangulations
From MaRDI portal
Publication:1775778
DOI10.1016/J.COMGEO.2004.07.003zbMATH Open1070.65014DBLPjournals/comgeo/HaasORSSSSSW05arXivmath/0307347OpenAlexW2953304270WikidataQ55920239 ScholiaQ55920239MaRDI QIDQ1775778FDOQ1775778
Authors: Ruth Haas, David Orden, Günter Rote, Brigitte Servatius, Ileana Streinu, Herman J. Servatius, Diane L. Souvaine, Walter Whiteley, Francisco Santos 
Publication date: 4 May 2005
Published in: Computational Geometry (Search for Journal in Brave)
Abstract: Pointed pseudo-triangulations are planar minimally rigid graphs embedded in the plane with pointed vertices (adjacent to an angle larger than 180 degrees. In this paper we prove that the opposite statement is also true, namely that planar minimally rigid graphs always admit pointed embeddings, even under certain natural topological and combinatorial constraints. We provide two proofs, which both yield efficient embedding algorithms. One based on Henneberg inductive constructions from combinatorial rigidity theory, the other on a generalization of Tutte's barycentric embeddings to directed graphs.
Full work available at URL: https://arxiv.org/abs/math/0307347
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)
Cites Work
- Generalized Nested Dissection
- Realization spaces of polytopes
- Applications of a Planar Separator Theorem
- Title not available (Why is that?)
- On graphs and rigidity of plane skeletal structures
- Title not available (Why is that?)
- Title not available (Why is that?)
- Efficient Planarity Testing
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- How to draw a planar graph on a grid
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- How to Draw a Graph
- Title not available (Why is that?)
- Convexity minimizes pseudo-triangulations
- Operations on rigid formations of autonomous agents
- A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid.
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Title not available (Why is that?)
- Convex drawings of planar graphs and the order dimension of 3-polytopes
- Straightening polygonal arcs and convexifying polygonal cycles
- Topologically sweeping visibility complexes via pseudotriangulations
- Tight degree bounds for pseudo-triangulations of points
- Convex Representations of Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Deformable free space tilings for kinetic collision detection.
- Title not available (Why is that?)
- Planar minimally rigid graphs and pseudo-triangulations
- Algorithms and Data Structures
- Spaces of stresses, projections and parallel drawings for spherical polyhedra
- Tutte's barycenter method applied to isotopies
- The structure of locally finite two-connected graphs
- The polytope of non-crossing graphs on a planar point set
- Title not available (Why is that?)
- Non-crossing frameworks with non-crossing reciprocals
- Title not available (Why is that?)
Cited In (43)
- Pointed spherical tilings and hyperbolic virtual polytopes
- Rigidity with few locations
- Mixed volume techniques for embeddings of Laman graphs
- 3-colorability of pseudo-triangulations
- The combinatorial geometry of stresses in frameworks
- Multitriangulations, pseudotriangulations and primitive sorting networks
- Non-convex Representations of Graphs
- Decompositions, partitions, and coverings with convex polygons and pseudo-triangles
- Combinatorial pseudo-triangulations
- Recognizing planar Laman graphs
- Minimally rigid periodic graphs
- Certifying and constructing minimally rigid graphs in the plane
- Structure of the set of planar minimal networks with given topology and boundary
- Topological inductive constructions for tight surface graphs
- Non-crossing frameworks with non-crossing reciprocals
- Graph Drawing
- Planar and Toroidal Morphs Made Easier
- Pointed drawings of planar graphs
- Vertex spanning planar Laman graphs in triangulated surfaces
- The polytope of non-crossing graphs on a planar point set
- The non-solvability by radicals of generic 3-connected planar Laman graphs
- On numbers of pseudo-triangulations
- Combinatorial and geometric properties of planar Laman graphs
- Algorithms – ESA 2004
- Title not available (Why is that?)
- Augmenting the rigidity of a graph in \(\mathbb R^{2}\)
- Planar minimally rigid graphs and pseudo-triangulations
- Rigid frameworks with dilation constraints
- On the number of pseudo-triangulations of certain point sets
- Matching edges and faces in polygonal partitions
- Contact Graphs of Circular Arcs
- Rigidity of frameworks on expanding spheres
- Angle covers: algorithms and complexity
- Resolving Loads with Positive Interior Stresses
- Vertex spanning planar Laman graphs in triangulated surfaces
- Connectivity augmentation in planar straight line graphs
- Spatial embedding of pseudo-triangulations
- Drawing planar cubic 3-connected graphs with few segments: algorithms \& experiments
- A Henneberg-based algorithm for generating tree-decomposable minimally rigid graphs
- A vertex-face assignment for plane graphs
- A note on \(l_ 1\)-rigid planar graphs
- Pseudo-triangulations -- a survey
- Exact camera location recovery by least unsquared deviations
This page was built for publication: Planar minimally rigid graphs and pseudo-triangulations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1775778)
