The Polytope of Non-Crossing Graphs on a Planar Point Set

摘要

For any finite set A of n points in general position 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 pointed 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 3n — 3 — 2n_b where n_b is the number of convex hull points of 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.