The polytope of non-crossing graphs on a planar point set

DOI10.1007/S00454-004-1143-1zbMATH Open1063.68077arXivmath/0302126OpenAlexW1977413884MaRDI QIDQ1772132FDOQ1772132

Authors: David Orden, Francisco Santos 

Publication date: 15 April 2005

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

Abstract: For any finite set $A$ of $n$ points in $R^2$, we define a $(3n-3)$-dimensional simple polyhedron whose face poset is isomorphic to the poset of ``non-crossing marked graphs with vertex set $A$, where a marked graph is defined as a geometric graph together with a subset of its vertices. The poset of non-crossing graphs on $A$ appears as the complement of the star of a face in that polyhedron. The polyhedron has a unique maximal bounded face, of dimension $2n_i+n-3$ where $n_i$ is the number of points of $A$ in the interior of $conv(A)$. The vertices of this polytope are all the pseudo-triangulations of $A$, and the edges are flips of two types: the traditional diagonal flips (in pseudo-triangulations) and the removal or insertion of a single edge. As a by-product of our construction we prove that all pseudo-triangulations are infinitesimally rigid graphs.

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

Recommendations

• The polytope of non-crossing graphs on a planar point set
• Planar minimally rigid graphs and pseudo-triangulations
• Planar minimally rigid graphs and pseudo-triangulations
• Enumerating pseudo-triangulations in the plane
• Combinatorial pseudo-triangulations

zbMATH Keywords

rigid graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Polytopes and polyhedra (52B99)

Cited In (16)

• A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set
• A proof of the orbit conjecture for flipping edge-labelled triangulations
• The complex of non-crossing diagonals of a polygon
• Planar minimally rigid graphs and pseudo-triangulations
• Non-crossing matchings of points with geometric objects
• Combinatorial pseudo-triangulations
• Pre-triangulations and liftable complexes
• Connectivity of triangulation flip graphs in the plane
• The polytope of non-crossing graphs on a planar point set
• Planar minimally rigid graphs and pseudo-triangulations
• On the number of plane geometric graphs
• On the number of pseudo-triangulations of certain point sets
• On minimum weight pseudo-triangulations
• Multitriangulations as complexes of star polygons
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices

This page was built for publication: The polytope of non-crossing graphs on a planar point set

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