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

*(English)*Zbl 1063.68077[An abridged version of this paper was published in Proc. 2004 Int. Symposium on Symbolic and Algebraic Computation, 250–257 (2004; Zbl 1134.05308).]

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

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

##### MSC:

68R10 | Graph theory (including graph drawing) in computer science |

05C10 | Planar graphs; geometric and topological aspects of graph theory |

52B99 | Polytopes and polyhedra |