Multi-triangulations as complexes of star polygons

Abstract

Maximal $(k+1)$-crossing-free graphs on a planar point set in convex position, that is, $k$-triangulations, have received attention in recent literature, with motivation coming from several interpretations of them. We introduce a new way of looking at $k$-triangulations, namely as complexes of star polygons. With this tool we give new, direct, proofs of the fundamental properties of $k$-triangulations, as well as some new results. This interpretation also opens-up new avenues of research, that we briefly explore in the last section.

40 pages, 24 figures; added references, update Section 8

References in corpus (1)

• Sparse Hypergraphs and Pebble Game Algorithms

Cited by in corpus (17)

• The diameter of associahedra
• The brick polytope of a sorting network
• Multitriangulations, pseudotriangulations and primitive sorting networks
• Brick polytopes of spherical subword complexes and generalized associahedra
• Subword complexes, cluster complexes, and generalized multi-associahedra
• A Hopf algebra of subword complexes
• Brick polytopes, lattice quotients, and Hopf algebras
• Fan realizations of subword complexes and multi-associahedra via Gale duality
• The diameter of type D associahedra and the non-leaving-face property
• Celebrating Loday's Associahedron
• Analytic combinatorics of chord and hyperchord diagrams with $k$ crossings
• Multitriangulations, pseudotriangulations and some problems of realization of polytopes
• Fan realizations for some 2-associahedra
• Realizations of multiassociahedra via rigidity
• Multitriangulations and tropical Pfaffians
• Wigglyhedra
• The greedy flip tree of a subword complex