# Mathematics Colloquia and Seminars

Adding marks to some vertices, we introduce the notion of marked graphs and pseudo-triangulations. We extend to them some properties of usual pseudo-triangulations, among them the notion of flips of interior edges between pointed vertices of a pseudo-triangulation to flips of any interior edge or mark of a marked pseudo-triangulation. These flips produce a graph whose vertices are all the pseudo-triangulations of the given point set, containing in particular all triangulations and pointed pseudo-triangulations. The graph is regular of degree $3i+b-3$, where $i$ and $b$ are the numbers of interior and boundary points in the point set We construct the polyhedron of marked non-crossing graphs of a point set in the plane, defined as a convenient perturbation of a polyhedral cone. Its 1-skeleton is the regular graph mentioned above. The face poset of the polyhedron is opposite to the poset of marked non-crossing graphs, so in particular we obtain a (sub)polyhedron whose face poset is the poset of non-crossing graphs.