Multitriangulations 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.

Review text

A \textit{multitriangulation} of order \(k\), or \(k\)-triangulation, of a convex \(n\)-gon is a maximal set of edges such that no \(k+1\) of them mutually cross. A \textit{flip} between \(k\)-triangulations creates one \(k\)-triangulation from another one, removing and inserting a single edge. The \textit{length} of an edge \([p_i,p_j]\) between \(n\) points \(p_1,\dots ,p_n\) in convex position and labeled cyclically is defined as \(\min\{|j - i|,|i - j |\}\) mod \(n\). If \(p,q\) are two coprime integers, a \textit{star-polygon} of type \(\{p/q\}\) is a polygon formed by connecting a set \(V=\{s_j\:|\:j\in\mathbb{Z}_p\}\) of \(p\) points on the unit circle with the set \(E=\{[s_j,s_{j+q}]\:|\:j\in \mathbb{Z}_p\}\). The notion of \(k\)-triangulation has been widely explored from many points of view. In this paper the authors introduce a new one, namely as complexes of star polygons of type \(\{2k+1/k\}\), called \textit{\(k\)-stars}. Let \(T\) be a \(k\)-triangulation of the \(n\)-gon, \(n\geq 2k+1\). The main results of the paper are the following (at the end of the paper the authors point out that such results have been independently discovered by \textit{A. Dress, S. Grünewald, J. Jonsson}, and \textit{V. Moulton}, in ``The simplicial complex \(\varDelta _{n,k}\) of \(k\)-compatible line arrangements in the hyperbolic plane. Part 1: The structure of \(\varDelta _{n,k}\), preprint (2007). {\parindent5mm \begin{itemize}\item[1)] \(T\) contains exactly \(n- 2k\) \(k\)-stars; \item[2)] each edge of \(T\) belongs to zero, one or two \(k\)-stars, depending on whether its length is smaller, equal or greater than \(k\); \item[3)] Any common edge \(f\) of two \(k\)-stars \(R\) and \(S\) of \(T\) can be flipped to another edge \(e\) so that \(T\triangle\{e,f\}\) is a \(k\)-triangulation. Moreover, the edges \(e\) and \(f\) depend only on \(R\cup S\), not the rest of \(T\). \end{itemize}} It is the authors' opinion that \(k\)-stars are the right way of looking at \(k\)-triangulations. As evidence for this, they also give new proofs of basic properties of \(k\)-triangulations, which, in contrast with the proofs previously appeared in the literature, are just based on simple combinatorial properties of \(k\)-stars. The paper ends with a discussion on possible developments of the new approach to further problems.

Recommendations

Cites work

Cited in

(27)

This page was built for publication: Multitriangulations as complexes of star polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1017914)