The polytope of non-crossing graphs on a planar point set
| dc.creator | Orden, David | |
| dc.creator | Santos, Francisco | |
| dc.date | 2003-02-11 | |
| dc.date | 2003-05-30 | |
| dc.date.accessioned | 2026-07-07T04:55:12Z | |
| dc.date.available | 2026-07-07T04:55:12Z | |
| dc.description | 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. | |
| dc.description | 28 pages, 16 figures. Main change from v1 and v2: Introduction has been reshaped | |
| dc.identifier | https://arxiv.org/abs/math/0302126 | |
| dc.identifier | http://arxiv.org/abs/math/0302126 | |
| dc.identifier | Discrete Comput. Geom. 33:2 (2005), 275-305 | |
| dc.identifier | doi:10.1007/s00454-004-1143-1 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/66498 | |
| dc.subject | Combinatorics | |
| dc.subject | Metric Geometry | |
| dc.subject | 05C10 (primary), 52C25 (secondary) | |
| dc.title | The polytope of non-crossing graphs on a planar point set | |
| dc.type | text |