Return to Colloquia & Seminar listing
The polyhedron of non-crossing graphs on a planar point set
Algebra & Discrete Mathematics| Speaker: | David Orden, Univ. of Cantabria |
| Location: | 693 Kerr |
| Start time: | Fri, Aug 2 2002, 10:00AM |
Description
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.