  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.
