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

For any finite set $\text{A}$ of $n$ points in ${\mathbb{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 $\text{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 $\text{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 $\text{A}$ in the interior of $\text{conv}(\text{A})$. The vertices of this polytope are all the pseudo-triangulations of $\text{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.