2003/02/28 by David Orden, Francisco Santos · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Point processes and geometric inequalities #math.CO #math.MG #msc:05C10 #msc:52C25
paper · pdf · doi:10.1007/s00454-004-1143-1
published as Discrete Comput. Geom. 33:2 (2005), 275-305 · 28 pages, 16 figures. Main change from v1 and v2: Introduction has been reshaped
arxiv created 2003/05/30 · openalex publication_date 2004/11/15 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For any finite set \A of n points in \R2, 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 2ni +n -3 where ni 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.