# Multi-triangulations as complexes of star polygons

Vincent Pilaud<fnref n="1" /> and Francisco Santos<fnref n="2" /> †

**Abstract.** A *k*-triangulation of a convex polygon is a maximal set of diagonals so that no *k* + 1 of them mutually cross. *k*-triangulations have received attention in recent literature, with motivation coming from several interpretations of them.

We present a new way of looking at *k*-triangulations, where certain star polygons naturally generalize triangles for *k*-triangulations. With this tool we give new, direct proofs of the fundamental properties of *k*-triangulations (number of edges, definition of flip). This interpretation also opens up new avenues of research that we briefly explore in the last section.

**Résumé.** Une *k*-triangulation d'un polygone convexe est un ensemble maximal de diagonales ne contenant pas *k* + 1 arêtes qui se croisent deux à deux. Les *k*-triangulations ont été récemment étudiées sous divers aspects dans la littérature.

On présente ici un nouveau point de vue sur les *k*-triangulations, en introduisant certains polygones étoilés comme généralisation des triangles pour les *k*-triangulations. En utilisant ce nouvel outil, on donne des preuves directes des propriétés fondamentales des *k*-triangulations (nombre d'arêtes, définition du flip). Notre point de vue ouvre par ailleurs de nouveaux horizons de recherche que l'on présente rapidement dans la dernière partie.

**Keywords:** generalized triangulation, crossing-free graph, star polygon

## 1 Introduction

A *multi-triangulation* 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. Multi-triangulations generalize triangulations of a convex *n*-gon (which correspond to the case *k* = 1).

As far as we know, multi-triangulations first appeared in the work of Capoyleas and Pach [CP92], who prove that a *k*-triangulation of a convex *n*-gon cannot have more than *k*(2*n* − 2*k* − 1) edges. Nakami-gawa [Nak00], and independently Dress, Koolen and Moulton [DKM02] then proved that all *k*-triangulations actually have that number of edges (for *n* ≥ 2*k* + 1). Both proofs use the concept of “flips”

<footnote n="1">¹ École Normale Supérieure, Paris, France</footnote>

<footnote n="2">² Universidad de Cantabria, Santander, Spain</footnote>

<footnote>†This paper was written while the first author was visiting the second one through an internship agreement between the École Normale Supérieure and the University of Cantabria. Research of both authors was also funded by grant MTM2005-08618-C02-02 of the Spanish Ministry of Education and Science.</footnote>
between $k$-triangulations. As the name suggests, a flip creates one $k$-triangulation from another one, removing and inserting a single edge. In fact, Nakamigawa [Nak00] shows that (almost) every edge of a $k$-triangulation can be flipped. To obtain this result, he uses a “deletion/insertion operation” that transforms $k$-triangulations of a convex $(n+1)$-gon into $k$-triangulations of a convex $n$-gon and vice-versa. More recently, Jonsson [Jon03, Jon05] proved that the set of $k$-triangulations is enumerated by the same “Catalan determinant” counting families of $k$ mutually non-crossing Dyck paths.

Here we propose a new way of looking at $k$-triangulations, via the following generalization of triangles:

**Definition 1** A $k$-star is a star polygon of type $\{\frac{2k+1}{k}\}$, that is, a polygon formed by connecting a set $V = \{s_j \mid j \in \mathbb{Z}_{2k+1}\}$ of $2k+1$ points cyclically ordered on the unit circle with the set $E = \{[s_j, s_{j+k}] \mid j \in \mathbb{Z}_{2k+1}\}$ (see Fig. 1).

<figure><img src="image_1.png" /><figcaption>Fig. 1: A 2-star and a 5-star.</figcaption></figure>

We prove in Section 4 that a $k$-triangulation $T$ of a convex $n$-gon contains exactly $n - 2k$ $k$-stars and that an edge of $T$ is adjacent to zero, one or two $k$-stars of $T$ according to whether its length is smaller, equal or greater than $k$. Thus, a $k$-triangulation can be seen as a complex of $k$-stars. Using this point of view, we give new proofs of the basic properties of $k$-triangulations (number of edges in Section 4, flips in Section 5): our proofs are direct and based on simple combinatorial properties of the mutual disposition of $k$-stars in a $(k+1)$-crossing-free graph, which we develop in Section 3. Another advantage of $k$-stars is that they allow for a much more explicit (and algorithmically better) way of understanding flips. Further properties and questions about $k$-triangulations that are (or may hopefully be) easier to analyze using $k$-stars are quickly discussed in Section 6.

After the completion of this paper we have found out that our main result (Section 4), has independently been discovered by Dress & al. [DGJM07].

## 2 Notation

Let $k$ and $n$ be two integers such that $k \ge 1$ and $n \ge 2k + 1$.

Let $V_n$ be the set of vertices of a convex $n$-gon, i.e. any set of points on the unit circle, labeled counterclockwise by the cyclic set $\mathbb{Z}_n$. For $u, v, w \in V_n$, we will write $u \prec v \prec w$ meaning that $u, v$ and $w$ are in counterclockwise order on the circle. For any $u, v \in V_n$, let $[u, v]$ denote the *cyclic interval* $\{w \in V_n \mid u \le w \le v\}$. The intervals $[u, v]$, $[u, v]$ and $[u, v]$ are defined similarly.

For $u \ne v \in V_n$, let $[u, v]$ denote the *edge* connecting the vertices $u$ and $v$. The *length* of the edge $[u, v]$ is $|u - v| = \min(|[u, v]|, |[v, u]|)$. Let $E_n = \binom{V_n}{2}$ be the set of edges of the complete graph on $V_n$. Two
edges $[u, v]$ and $[u', v']$ are said to cross when the straight open segments $(u, v)$ and $(u', v')$ intersect. For $\ell \in \mathbb{N}$, an $\ell$-crossing is a set of $\ell$ mutually intersecting edges.

**Definition 2** A $k$-triangulation of the $n$-gon is a maximal $(k+1)$-crossing-free subset of $E_n$.

Obviously, an edge $[u, v]$ of $E_n$ can appear in a $(k+1)$-crossing only if $|u-v| > k$. We say that such an edge is *k-relevant*. We say that an edge $[u, v]$ is a *k-boundary* if $|u-v| = k$ and that it is *k-irrelevant* if $|u-v| < k$. Every $k$-triangulation of the $n$-gon consists of all the $kn$ $k$-irrelevant plus $k$-boundary edges and some $k$-relevant edges.

An angle $\angle(u, v, w)$ of a subset $E$ of $E_n$ is a pair $\{[u, v], [v, w]\}$ of edges of $E$ such that $u \prec v \prec w$ and for all $t \in \mathbb{W}, u\llcorner, w, u\lrcorner$, the edge $[v, t]$ is not in $E$. We call $v$ the *vertex* of the angle $\angle(u, v, w)$. If $t \in \mathbb{W}, w, u\llcorner$, we say that $t$ is contained in $\angle(u, v, w)$, and that the edge $[v, t]$ is a *bisector* of $\angle(u, v, w)$. An angle is said to be *k-relevant* if both its edges are either $k$-relevant or $k$-boundary edges.

As stated in the introduction, a $k$-star is a set of edges of the form $\{[s_j, s_{j+k}] \mid j \in \mathbb{Z}_{2k+1}\}$, where $s_0 \prec s_1 \prec \dots \prec s_{2k} \prec s_0$ are cyclically ordered. Note that there are two natural cyclic orders on the vertices of a $k$-star $S$: the *circle order*, defined as the cyclic order around the circle, and the *star order*, defined as the cyclic order tracing the edges of $S$. More precisely, if $s_0, \dots, s_{2k}$ are the vertices of $S$ cyclically ordered around the circle, we rename the vertices $r_i = s_{ik}$ to obtain the star order $r_0, \dots, r_{2k}$.

## 3 Mutual positions of $k$-stars

In this section, we study the mutual position of two $k$-stars $R$ and $S$ of a $(k+1)$-crossing-free subset $E$ of $E_n$.

**Lemma 3** (i) Any vertex $t$ not in $S$ is contained in a unique angle $\angle(u, v, w)$ of $S$.

(ii) Any angle of $S$ is also an angle of $E$ and is $k$-relevant.

(iii) $R$ and $S$ can not share any angle.

**Proof:** Part (i) is obvious.

Part (ii) just says differently that adding one of its bisectors to a $k$-star creates a $(k+1)$-crossing.

Observe that it implies that the knowledge of one angle of $S$ permits the recovery of all the $k$-star $S$. Indeed, if $\angle(s_0, s_1, s_2)$ is an angle of $S$, we define recursively $s_j$ as the unique vertex such that $\angle(s_{j-2}, s_{j-1}, s_j)$ is an angle of $E$ (i.e. $s_j$ is the first neighbor of $s_{j-1}$ after $s_{j-2}$ when rotating clockwise). Then $s_0, \dots, s_{2k}$ are the vertices of $S$ in star order.

Part (iii) thus follows immediately. $\square$

In the following statement and the rest of the paper, a *bisector* of $S$ is a bisector of an angle of $S$.

**Theorem 4** Every pair of $k$-stars whose union is $(k+1)$-crossing-free have a unique common bisector.

**Proof:** In order to prove existence, we consider the dual of a $k$-star: the set $\ell_R$ (resp. $\ell_S$) of all geometric bisectors of $R$ (resp. $S$) – including the edges of $R$ (resp. $S$) as limit cases – is a pseudoline in the Möbius strip, that is, a non-separating simple closed curve of the Möbius strip. The two pseudolines $\ell_R$ and $\ell_S$ can have contact points (corresponding to common edges) and crossing points (corresponding to common
bisectors). Since two pseudolines in the Möbius strip have at least one crossing point, the two k-stars R and S have at least one common bisector.

Suppose now that we have two different common bisectors e and f of R and S, and let {$r_j | j \in \mathbb{Z}_{2k+1}$} and {$s_j | j \in \mathbb{Z}_{2k+1}$} denote the vertices of R and S in star order labeled so that $e = [r_0, s_0]$. Let $a, b \in \mathbb{Z}_{2k+1}$ such that $f = [r_a, s_b]$. Note that certainly, $a \neq 0$, $b \neq 0$, and $a$ and $b$ have the same parity. By symmetry, we can assume that $a = 2\alpha$, $b = 2\beta$ with $1 \le \beta \le \alpha \le k$. But then the set

$$ \{[r_{2i}, r_{2i+1}] | 0 \le i \le \alpha - 1\} \cup \{[s_{2j}, s_{2j+1}] | \beta \le j \le k\} $$

forms a $(k + 1 + \alpha - \beta)$-crossing, and $k + 1 + \alpha - \beta \ge k + 1$. This proves uniqueness. $\square$

<figure><img src="image_2.png" /><figcaption>Fig. 2: The common bisector of two 2-stars (left) and a 2-crossing that crosses it (right).</figcaption></figure>

In the following lemmas, {$r_j | j \in \mathbb{Z}_{2k+1}$} and {$s_j | j \in \mathbb{Z}_{2k+1}$} denote the vertices of R and S, in star order, with $e = [r_0, s_0]$ being the common bisector of R and S (see Fig. 2).

**Lemma 5** For every $1 \le i \le k$, $r_{2i-1} \in \mathbb{Z}_{2k+1}$ and $s_{2i-1} \in \mathbb{Z}_{2k+1}$, $s_0 \in \mathbb{Z}_{2k+1}$, $r_0 \in \mathbb{Z}_{2k+1}$, $r_{2i} \in \mathbb{Z}_{2k+1}$ and $s_{2i} \in \mathbb{Z}_{2k+1}$, $s_0 \in \mathbb{Z}_{2k+1}$, $r_{2i+1} \in \mathbb{Z}_{2k+1}$ and $s_{2i+1} \in \mathbb{Z}_{2k+1}$ do not cross.

**Proof:** Suppose that there exists $1 \le i \le k$ such that $r_{2i-1} \in \mathbb{Z}_{2k+1}$, $s_0 \in \mathbb{Z}_{2k+1}$ or $s_{2i-1} \in \mathbb{Z}_{2k+1}$, $r_0 \in \mathbb{Z}_{2k+1}$. Let $\gamma$ be the highest such integer, and assume for example that $r_{2\gamma-1} \in \mathbb{Z}_{2k+1}$, $s_0 \in \mathbb{Z}_{2k+1}$. Then the definition of $\gamma$ ensures that $s_0 < s_{2\gamma+1} < r_{2\gamma+2} < r_{2\gamma-2}$ so that the set

$$ \{[r_{2i}, r_{2i+1}] | 0 \le i \le \gamma - 1\} \cup \{[s_{2j}, s_{2j+1}] | \gamma \le j \le k\} $$

forms a $(k + 1)$-crossing. $\square$

The previous lemma can be read as stating that corresponding edges of R and S are parallel. It is easy to see that $k$ of these $2k + 1$ pairs of parallel edges, the ones of form $([r_{2i-1}, r_{2i}], [s_{2i-1}, s_{2i}])$ with $1 \le i \le k$, separate R from S, meaning that the majority of the vertices of R lie in $[r_{2i}, r_{2i-1}]$ while the majority of the vertices of S lie in $[s_{2i}, s_{2i-1}]$. The next lemma says that any k-crossing that, in turn, crosses the common bisector $e = [r_0, s_0]$ has one edge parallel to and between each such pair (see Fig. 2).
**Lemma 6** Let F be a k-crossing of E such that all its edges cross $e = [r_0, s_0]$. Let $f_1 = [x_1, y_1], \dots, f_k = [x_k, y_k]$ denote the edges of F, with $r_0 \prec x_1 \prec \dots \prec x_k \prec s_0 \prec y_1 \prec \dots \prec y_k \prec r_0$. Then for any $1 \le i \le k$, we have $x_i \in [r_{2k-2i+1}, s_{2k-2i+2}]$ and $y_i \in [s_{2k-2i+1}, r_{2k-2i+2}]$.

**Proof:** Suppose that there exists $1 \le i \le k$ such that $r_0 \prec x_i \prec r_{2k-2i+1}$ and let

$$ \ell = \max\{1 \le i \le k \mid r_0 \prec x_i \prec r_{2k-2i+1}\}. $$

If $\ell = k$, then the set $\{e_1, \dots, e_k, [r_0, r_1]\}$ is a $(k+1)$-crossing of E, thus we assume that $\ell < k$. In order for

$$ \{e_1, \dots, e_\ell\} \cup \{[r_0, r_1], \dots, [r_{2k-2\ell}, r_{2k-2\ell+1}]\} $$

not to be a $(k+1)$-crossing, we have $r_{2k-2\ell} \prec y_\ell \prec r_0$, so that $r_{2k-2\ell} \prec y_{\ell+1} \prec r_0$. But the definition of $\ell$ implies that $r_{2k-2\ell+1} \prec r_{2k-2\ell-1} \prec x_{\ell+1} \prec s_0$, so that the set

$$ \{[r_{2k-2\ell}, r_{2k-2\ell+1}], \dots, [r_{2k-2}, r_{2k-1}], [r_{2k}, r_0]\} \cup \{e_{\ell+1}, \dots, e_k\} $$

is a $(k+1)$-crossing of E.

By symmetry, the lemma is proved.

□

The following lemma is at the heart of the concept of flips, that will be studied further in Section 5. As usual, we use the symbol $\triangle$ for symmetric difference.

**Lemma 7** Let $f$ be a common edge of $R$ and $S$. Then

(i) there exists $1 \le i \le k$ such that $f = [r_{2i-1}, r_{2i}] = [s_{2i}, s_{2i-1}]$;

(ii) $E \Delta \{e, f\}$ is a $(k+1)$-crossing-free subset of $E_n$;

(iii) $s_0, \dots, s_{2i-2}, s_{2i-1} = r_{2i}, r_{2i+1}, \dots, r_{2k}, r_0$ (resp. $r_0, \dots, r_{2i-2}, r_{2i-1} = s_{2i}, s_{2i+1}, \dots, s_{2k}, s_0$) are the vertices of a k-star $X$ (resp. $Y$) of $E \Delta \{e, f\}$, in star order;

(iv) $X$ and $Y$ share the edge $e$ and their common bisector is $f$.

**Proof:** Let $u$ and $v$ denote the vertices of $f$. Lemma 5 ensures that $\{r_0, s_0\} \cap \{u, v\} = \emptyset$ so that we can assume $r_0 \prec u \prec s_0 \prec v \prec r_0$. Consequently, there exists $1 \le i, j \le k$ such that $u = r_{2i-1} = s_{2j}$ and $v = r_{2i} = s_{2j-1}$. Suppose that $i > j$. Then according to Lemma 5, we have $r_0 \prec r_{2i-1} \prec s_{2i} \prec s_{2j} = r_{2i-1}$ which is impossible. We obtain that $i = j$ and $f = [r_{2i-1}, r_{2i}] = [s_{2i}, s_{2i-1}]$.

Lemma 6 then proves that any k-crossing of $T$ that prevents $e$ from being in $T$ contains $f$, so that $T \Delta \{e, f\}$ is $(k+1)$-crossing-free.

Let $L$ be the list of vertices $(s_0, \dots, s_{2i-2}, r_{2i}, \dots, r_{2k}, r_0)$. Between two consecutive elements of $L$ lie exactly $k-1$ other points of $L$ (for the circle order). This implies that $L$ is in star order. Part (iii) thus follows from the fact that any edge connecting two consecutive points of $L$ is in $E \Delta \{e, f\}$.

The edge $e$ is clearly common to $X$ and $Y$. The edge $f$ is a bisector of both angles $\angle(r_{2i-2}, r_{2i-1}, s_{2i+1})$ and $\angle(s_{2i-2}, s_{2i-1}, r_{2i+1})$, so that it is the common bisector of $X$ and $Y$. □
# 4 $k$-triangulations as complexes of $k$-stars

In this section, $T$ is a $k$-triangulation of the $n$-gon, i.e. a maximal ($k+1$)-crossing-free subset of $E_n$. Remember that any angle of a $k$-star contained in $T$ is a $k$-relevant angle of $T$ (Lemma 3(2)). Results of this paper are based on the converse of this statement:

**Theorem 8** Any $k$-relevant angle of $T$ belongs to a unique $k$-star contained in $T$.

**Proof:** In this proof, we need the following definition (see Fig. 3): let $\angle(u, v, w)$ be a $k$-relevant angle of $T$ and let $e$ and $f$ be two edges of $T$ that intersect $\angle(u, v, w)$ (i.e. that intersect both $[u, v]$ and $[v, w]$). If $a, b, c$ and $d$ denote their vertices such that $u \prec a \prec v \prec b \prec w$ and $u \prec c \prec v \prec d \prec w$, then we say that $e = [a, b]$ is $v$-farther than $f = [c, d]$ if $u \prec a \preceq c \prec v \prec d \preceq b \prec w$. Let $E$ and $F$ be two ($k-1$)-crossings that intersect $\angle(u, v, w)$. Let their edges be labeled $e_1 = [a_1, b_1]$, $e_2 = [a_2, b_2]$, ..., $e_{k-1} = [a_{k-1}, b_{k-1}]$ and $f_1 = [c_1, d_1]$, $f_2 = [c_2, d_2]$, ..., $f_{k-1} = [c_{k-1}, d_{k-1}]$ such that $u \prec a_1 \prec a_2 \prec \dots \prec a_{k-1} \prec v \prec b_1 \prec b_2 \prec \dots \prec b_{k-1} \prec w$ and $u \prec c_1 \prec c_2 \prec \dots \prec c_{k-1} \prec v \prec d_1 \prec d_2 \prec \dots \prec d_{k-1} \prec w$. Then we say that $E$ is $v$-farther than $F$ if $e_i$ is $v$-farther than $f_i$ for every $1 \le i \le k-1$. We say that $E$ is $v$-maximal if there is no ($k-1$)-crossing intersecting $\angle(u, v, w)$ and $v$-farther than $E$.

<figure><img src="image_3.png" /><figcaption>**Fig. 3:** $[a, b]$ is $v$-farther than $[c, d]$ (left) and $[[a_i, b_i]]$ is $v$-farther than $[[c_i, d_i]]$ (right).</figcaption></figure>

We can now give the proof of Theorem 8. Let $\angle(u, v, w)$ be a $k$-relevant angle of $T$. It is easy to check that we can assume that the edge $[u, v+1]$ is not in $T$. This implies that we have a $k$-crossing $E$ of the form $e_1 = [a_1, b_1]$, ..., $e_k = [a_k, b_k]$ with $u \prec a_1 \prec \dots \prec a_k \prec v+1$ and $v+1 \prec b_1 \prec \dots \prec b_k \prec u$. This provides a ($k-1$)-crossing $\{e_1, \dots, e_{k-1}\}$ intersecting $\angle(u, v, w)$ (see Fig. 4(a)). We prove that if we choose this ($k-1$)-crossing to be $v$-maximal, then the edges $[u, b_1]$, $[a_1, b_2]$, ..., $[a_{k-2}, b_{k-1}]$, $[a_{k-1}, w]$ are in $T$ such that the points $u, a_1, \dots, a_{k-1}, v, b_1, \dots, b_{k-1}, w$ are the vertices of a $k$-star of $T$ containing the angle $\angle(u, v, w)$. To get this result, we use two steps: first we prove that $\angle(a_1, b_1, u)$ is an angle of $T$, and then we prove that the edges $e_2, \dots, e_{k-1}, [v, w]$ form a ($k-1$)-crossing intersecting $\angle(a_1, b_1, u)$ and $b_1$-maximal (so that we can reiterate the argument).

**FIRST STEP.** (see Fig. 4(b))

Suppose that $[u, b_1]$ is not in $T$. Thus we have a $k$-crossing $F$ that prevents the edge $[u, b_1]$. Let $f_1 = [c_1, d_1]$, ..., $f_k = [c_k, d_k]$ denote its edges with $u \prec c_1 \prec \dots \prec c_k \prec b_1$ and $b_1 \prec d_1 \prec \dots \prec d_k \prec u$.

Note first that $v \prec d_k \preceq w$. Indeed, if it is not the case, then $d_k \in ]w, u]$ and $c_k \ne v$, because $\angle(u, v, w)$ is an angle. Thus either $c_k \in ]u, v]$ and then $F \cup \{[u, v]\}$ forms a ($k+1$)-crossing, or $c_k \in ]v, b_1]$ and then $E \cup \{[c_k, d_k]\}$ forms a ($k+1$)-crossing. Consequently, we have $b_1 \prec d_1 \prec \dots \prec d_{k-1} \prec w$.
<figure><img src="image_4.png" /><figcaption>Fig. 4: Illustration of proof of Theorem 8.</figcaption></figure>

Let $\ell = \max\{1 \le j \le k-1 \mid b_i \prec d_i \prec w$ for any $i$ with $1 \le i \le j\}$. Then for any $1 \le i \le \ell$, since $\{e_1, \dots, e_i\} \cup \{f_i, \dots, f_k\}$ does not form a $(k+1)$-crossing, we have $u \prec c_i \prec a_i$. Thus for any $1 \le i \le \ell$, $u \prec c_i \prec a_i \prec v \prec b_i \prec d_i \prec w$, so that $f_i$ is $v$-farther than $e_i$. Furthermore, we have $u \prec c_1 \prec \dots \prec c_\ell \prec a_{\ell+1} \prec \dots \prec a_{k-1} \prec v \prec d_1 \prec \dots \prec d_\ell \prec b_{\ell+1} \prec \dots \prec b_{k-1} \prec w$. Consequently, we get a $(k-1)$-crossing $\{f_1, \dots, f_\ell, e_{\ell+1}, \dots, e_{k-1}\}$ which is $v$-farther than $\{e_1, \dots, e_{k-1}\}$; this contradicts our supposition of $\{e_1, \dots, e_{k-1}\}$. Thus we obtain $[u, b_1] \in T$.

Suppose now that $\angle(a_1, b_1, u)$ is not an angle of $T$. Then there exists $a_0 \in \mathbb{Q}[u, a_1]$, such that $[b_1, a_0] \in T$. But then the $(k-1)$-crossing $\{[a_0, b_1], e_2, \dots, e_{k-1}\}$ is $v$-farther than $\{e_1, \dots, e_{k-1}\}$. This implies that $\angle(a_1, b_1, u)$ is an angle of $T$.

SECOND STEP. (see Fig. 4(c))

Let $F$ be a $(k-1)$-crossing intersecting $\angle(a_1, b_1, u)$ and $b_1$-farther than $\{e_2, \dots, e_{k-1}, [v, w]\}$. Let $f_2 = [c_2, d_2], \dots, f_k = [c_k, d_k]$ denote its edges, with $a_1 \prec c_2 \prec \dots \prec c_k \prec b_1 \prec d_2 \prec \dots \prec d_k \prec u$.

Note first that $b_k \prec d_k \prec w$. Indeed, if it is not the case, then $d_k \in \mathbb{Q}[w, u]$ and $c_k \neq v$, because $\angle(u, v, w)$ is an angle. Thus either $c_k \in \mathbb{Q}[a_1, v]$ and then $F \cup \{[u, v], e_1\}$ forms a $(k+1)$-crossing, or $c_k \in \mathbb{Q}[v, b_1]$ and then $E \cup \{[c_k, d_k]\}$ forms a $(k+1)$-crossing. Consequently, we have $b_1 \prec d_2 \prec \dots \prec d_{k-1} \prec w$.

Furthermore, for any $2 \le i \le k-1$, $f_i$ is $\angle(a_1, b_1, u)$-farther than $e_i$, so that $a_1 \prec c_i \prec a_i \prec b_1 \prec b_i \prec d_i \prec u$. In particular, $a_1 \prec c_{k-1} \prec a_{k-1} \prec v$ and we get $u \prec a_1 \prec c_2 \prec \dots \prec c_{k-1} \prec v \prec b_1 \prec d_2 \prec \dots \prec d_{k-1} \prec w$. Consequently, the $(k-1)$-crossing $\{e_1, f_2, \dots, f_{k-1}\}$ is $v$-farther than $\{e_1, \dots, e_{k-1}\}$, which is a contradiction. $\square$

The following easy consequence of Theorem 8 justifies the title of this paper.

**Corollary 9** Let $e$ be an edge of $T$.

(i) If $e$ is a $k$-relevant edge, then it belongs to exactly two $k$-stars of $T$ (one on each side);

(ii) If $e$ is a $k$-boundary edge, then it belongs to exactly one $k$-star of $T$ (on its "inner" side);

(iii) If $e$ is a $k$-irrelevant edge, then it does not belong to any $k$-star of $T$.

**Corollary 10** (i) For any $k$-star $S$ in $T$ and for any vertex $r$ not in $S$ there is a unique $k$-star $R$ in $T$ such that $r$ is a vertex of the common bisector of $R$ and $S$.
(ii) Any $k$-relevant edge which is not in $T$ is the common bisector of a unique pair of $k$-stars of $T$.

**Proof:** Let $\angle(u, s, v)$ be the unique angle of $S$ which contains $r$. Let $\angle(x, r, y)$ be the unique angle of $T$ of vertex $r$ which contains $s$. According to Theorem 8, the angle $\angle(x, r, y)$ belongs to a unique $k$-star $R$. The common bisector of $R$ and $S$ is $[r, s]$ and $R$ is the only such $k$-star of $T$.

Let $e = [r, s]$ be a $k$-relevant edge, not in $T$. Let $\angle(x, r, y)$ (resp. $\angle(u, s, v)$) denote the unique angle of $T$ of vertex $r$ (resp. $s$) which contains $s$ (resp. $r$). According to Theorem 8, the angle $\angle(x, r, y)$ (resp. $\angle(u, s, v)$) belongs to a unique $k$-star $R$ (resp. $S$). The common bisector of $R$ and $S$ is $[r, s]$ and $(R, S)$ is the only such couple of $k$-stars of $T$. $\square$

Observe that parts (i) and (ii) of this corollary give bijections between

(i) “vertices not used in the $k$-star $S$ of $T$” and “$k$-stars of $T$ different from $S$”;

(ii) “$k$-relevant edges not used in $T$” and “pairs of $k$-stars of $T$”.

From any of these two bijections, and using Corollary 9 for double counting, it is easy to derive the number of $k$-stars and of $k$-relevant edges in $T$:

**Corollary 11** (i) Any $k$-triangulation of the $n$-gon contains exactly $n - 2k$ $k$-stars, $k(n - 2k - 1)$ $k$-relevant edges and $k(2n - 2k - 1)$ edges.

(ii) The $k$-triangulations are exactly the $(k+1)$-crossing-free subsets of $E_n$ of cardinality $k(2n-2k-1)$.

Even if Part (ii) of this corollary was already known in [Nak00, DKM02], the study of $k$-triangulations as complexes of $k$-stars gives a much more direct proof of this result (all previous proofs were based on flips).

# 5 The graph of flips

Let $T$ be a $k$-triangulation of the $n$-gon, let $f$ be a $k$-relevant edge of $T$, let $R$ and $S$ be the two $k$-stars of $T$ containing $f$ (Corollary 9), and let $e$ be the common bisector of $R$ and $S$. Remember that we proved (Lemma 7) that $T\Delta\{e, f\}$ is a $(k+1)$-crossing-free subset of $E_n$. Observe moreover that Corollary 11 ensures that $T\Delta\{e, f\}$ is maximal. Thus, $T\Delta\{e, f\}$ is a $k$-triangulation of the $n$-gon.

**Lemma 12** *T and $T\Delta\{e, f\}$ are the only two $k$-triangulations of the $n$-gon containing $T \setminus \{f\}$.*

**Proof:** Let $e'$ be any edge of $E_n \setminus T$ distinct from $e$. Let $R'$ and $S'$ be the two $k$-stars with common bisector $e'$ (Corollary 10(ii)). We can assume that $R'$ does not contain $f$ and then $R' \cup \{e'\}$ is contained in $T\Delta\{e', f\}$ and forms a $(k+1)$-crossing. $\square$

We say that we obtain the $k$-triangulation $T\Delta\{e, f\}$ from the $k$-triangulation $T$ by *flipping* the edge $f$. Again, the notion of flip in $k$-triangulations was already known and used in [Nak00, DKM02], but $k$-stars allows a local (thus, better) comprehension of flips.

Let $G_{n,k}$ be the *graph of flips* on the set of $k$-triangulations of the $n$-gon, i.e. the graph whose vertices are the $k$-triangulations of the $n$-gon and whose edges are the pairs of $k$-triangulations related by a flip. It follows from Corollary 11 and Lemma 12 that $G_{n,k}$ is regular of degree $k(n - 2k - 1)$: every $k$-relevant
edge of $T$ can be flipped, in a unique way. In this section, we prove the connectivity of this graph and bound its diameter.

Note that $e$ and $f$ necessarily cross. In particular, if $e = [\alpha, \beta]$ and $f = [\gamma, \delta]$, with $0 \le \alpha < \beta \le n-1$ and $0 \le \gamma < \delta \le n-1$, then either $0 \le \alpha < \gamma < \beta < \delta \le n-1$ (and the flip is said to be *slope-decreasing*), or $0 \le \gamma < \alpha < \delta < \beta \le n-1$ (and the flip is said to be *slope-increasing*). We define a partial order on the set of $k$-triangulations of the $n$-gon as follows: for two $k$-triangulations $T$ and $T'$, we say $T < T'$ if and only if there exists a sequence of slope-increasing flips from $T$ to $T'$. That this is indeed a partial order follows from the fact that each slope-increasing flip increases the *total slope* of a $k$-triangulation, where the slope of an edge $[u, v]$ is defined as $u + v$ (with the sum taken in $\mathbb{N}$, not in $\mathbb{Z}_n$) and the total slope of a $k$-triangulation is the sum of the slopes of its edges.

Let $T_{n,k}^{\min}$ be the $k$-triangulation of the $n$-gon whose set of $k$-relevant edges is

$$ \{[i, j] \mid i \in \llbracket 0, k-1 \rrbracket \text{ and } j \in \llbracket i+k+1, i-k \rrbracket - 1 \}. $$

<figure><img src="image_5.png" /><figcaption>Fig. 5: Triangulation $T_{11,3}^{\min}$.</figcaption></figure>

**Lemma 13** For any $k$-triangulation of the $n$-gon $T \neq T_{n,k}^{\min}$, there exists a $k$-relevant edge $f \in T \setminus T_{n,k}^{\min}$ such that the edge added by the flip of $f$ is in $T_{n,k}^{\min}$.

In particular, the $k$-triangulation $T_{n,k}^{\min}$ is the unique least element of the set of $k$-triangulations of the $n$-gon, partially ordered by $<$.

**Proof:** Since the second part is an immediate corollary of the first one, we only have to prove the first part.

Let $T$ be a $k$-triangulation of the $n$-gon distinct from $T_{n,k}^{\min}$. Let

$$ \ell = \max\{k+1 \le i \le n-k-1 \mid \{[0, i], [1, i+1], \dots, [k-1, i+k-1]\} \not\subseteq T\}, $$

which exists because $T \neq T_{n,k}^{\min}$.

Let $0 \le j \le k-1$ such that the edge $[j, \ell+j]$ is not in $T$. Let $\{[x_1, y_1], \dots, [x_k, y_k]\}$ denote a $k$-crossing that prevents $[j, \ell+j]$ from being in $T$, with the convention that
(i) $x_1 < \dots < x_k < y_1 < \dots < y_k,$

(ii) if $j > 0$, then $j \in \llbracket x_j, x_{j+1} \rrbracket$ and $\ell + j \in \llbracket y_j, y_{j+1} \rrbracket,$

(iii) if $j = 0$, then $0 \in \llbracket y_k, x_1 \rrbracket$ and $\ell \in \llbracket x_k, y_1 \rrbracket$.

With this convention, we are sure that $x_k \in \llbracket k, \ell - 1 \rrbracket$ and $y_k \in \llbracket \ell + k, n - 1 \rrbracket$. If $y_k \in \ell + k, n - 1 \rrbracket$, then the set

$$ \{[0, \ell + 1], \dots, [k - 1, \ell + k], [x_k, y_k]\} $$

is a $(k+1)$-crossing of $T$. Thus $y_k = \ell + k$, and there exists an edge $[x_k, \ell + k]$ with $x_k \in \llbracket k, \ell - 1 \rrbracket$.

Now let $m = \min\{k \le i \le \ell - 1 \mid [i, \ell + k] \in T\}$. Let $f$ be the edge $[m, \ell + k]$, let $S$ be the $k$-star containing the angle $\angle(m, \ell+k, k-1)$ and let $R$ be the other $k$-star containing $f$. Let $s_0, \dots, s_{k-2}, s_{k-1} = k-1, s_k = m, s_{k+1}, \dots, s_{2k-1}, s_{2k} = \ell + k$ denote the vertices of the $k$-star $S$ in circle order. Then $s_0 \in \llbracket \ell + k + 1, 0 \rrbracket$, and the only way not to get a $(k+1)$-crossing is to have $s_0 = 0$. This implies that $s_j = j$ for all $0 \le j \le k-1$.

Let $e$ be the common bisector of $R$ and $S$ and $s$ denote its vertex in $S$. Since $f = [m, \ell + k] = [s_k, s_{2k}]$ is a common edge of $R$ and $S$, it is obvious that $s \notin \{s_k, s_{2k}\}$. Moreover, since for any $0 \le j \le k-1$ the interval $[s_j, s_{j+1}]$ is empty, $s \notin \{s_{k+1}, s_{k+2}, \dots, s_{2k-1}\}$. Consequently, $s \in \{s_0, \dots, s_{k-1}\} = \llbracket 0, k-1 \rrbracket$ and $e \in T_{n,k}^{\min} \setminus T$. $\square$

Obviously, we get symmetric results with the $k$-triangulation $T_{n,k}^{\max}$ whose set of $k$-relevant edges is $\{[i, j] \mid i \in \llbracket n-k, n-1 \rrbracket$ and $j \in \llbracket i+k+1, i-k \rrbracket\} - \{1, \dots, k\}$.

**Corollary 14** The graph $G_{n,k}$ is connected, regular of degree $k(n - 2k - 1)$, and its diameter is at most $2k(n - 2k - 1)$.

**Proof:** Let $T$ be a $k$-triangulation of the $n$-gon. The regularity follows from the fact that any of the $k(n - 2k - 1)$ $k$-relevant edges of $T$ can be flipped. Moreover, the previous lemma ensures that there exists a sequence of at most $k(n - 2k - 1)$ slope-decreasing flips from $T$ to $T_{n,k}^{\min}$. Thus any pair of $k$-triangulations is linked by a path of length at most $2k(n - 2k - 1)$ passing through $T_{n,k}^{\min}$. $\square$

Obviously we would obtain the same result with any rotation of the labeling of $V_n$. In particular, for any pair $\{T, T'\}$ of $k$-triangulations, we can choose the intermediate $k$-triangulation $T''$ for our path among any rotation of $T_{n,k}^{\min}$. Consequently, there exists a path linking $T$ and $T'$ of length smaller than the average of $|T \Delta T''| + |T'' \Delta T'|$ (for $T''$ among the rotations of $T_{n,k}^{\min}$). As proved in [Nak00], this argument improves the upper bound for the diameter to be $2k(n - 4k - 1)$ when $n > 8k^3 + 4k^2$.

Note that even if the improvement is asymptotically not relevant, for the case $k = 1$, the improved bound of $2n - 10$ is actually the exact diameter of the associahedron for large values of $n$ [STT88]. For $k > 1$, we only have the following lower bound:

**Lemma 15** If $n \ge 4k$, then the diameter of $G_{n,k}$ is at least $k(n - 2k - 1)$.

**Proof:** It is easy to construct two $k$-triangulations of the $n$-gon without any edge in common. $\square$

We want to observe that Lemma 13 is the way in which [Nak00] and [DKM02] prove that the number of edges in all $k$-triangulations of the $n$-gon is the same. Compare it to our direct proof in Corollary 11.
# 6 Further topics and open questions

In this section, we discuss further topics and open questions related to multi-triangulations. Let us begin with sketching two results that we do not develop in this paper for reasons of space (we refer to the full version of this paper [PS07] for more details):

**k-ears and k-colorable k-triangulations.** Let us assume that $n \ge 2k + 3$. We call a *k-ear* any edge of length $k + 1$ in a *k-triangulation*. We say that a *k-star* is *external* if it contains at least one *k-boundary* edge (and *internal* otherwise).

It is well known and easy to prove that the number of ears in any triangulation equals its number of internal triangles plus 2. We obtain similarly that the number of *k-ears* in a *k-triangulation* *T* equals the number of internal *k-stars* plus 2k. In particular, *T* contains at least 2k *k-ears*.

We also have a characterization of *k-triangulations* with exactly 2k *k-ears*: they are exactly the *k-triangulations* whose *k-relevant edges* can be colored with *k* colors without any monochromatic 2-crossing.

**Flattening an external k-star; inflating a k-crossing.** As mentioned in Section 1, there is a “deletion/insertion operation” that transforms a *k-triangulation* of the (*n* + 1)-gon into a *k-triangulation* of the *n*-gon, and vice-versa. This operation, which is useful for recursive arguments and was a step in all previous proofs of the flipability of *k-relevant edges* (Corollary 14), can be explained in terms of *k-stars*. Indeed, given an external *k-star* of a *k-triangulation* of the (*n* + 1)-gon, one can flatten it into a *k-crossing* and obtain a *k-triangulation* of the *n*-gon. Reciprocally, given a *k-crossing* using *k* consecutive vertices of a *k-triangulation* of the *n*-gon, one can inflate it into a *k-star* and obtain a *k-triangulation* of the (*n* + 1)-gon.

Let us now present three open questions that may hopefully be easier to prove and understand looking at *k-triangulations* as “complexes of *k-stars*”:

**The number of k-triangulations.** Remember that Jonsson proved in [Jon03] that the number of *k-triangulations* of the *n*-gon is equal to the determinant $\det(C_{n-i-j})_{1\le i,j\le k}$, where $C_m = \frac{1}{m+1}\binom{2m}{m}$ denotes the *m*-th *Catalan number*. This determinant is also known [DCV86] to enumerate the Dyck *k-paths* of semi-length $n-2k$, that is, the *k-tuples* $(d_1, \dots, d_k)$ of Dyck paths of semi-length $n-2k$ such that each $d_i$ never goes above $d_{i-1}$, for $2 \le i \le k$. But we know an explicit bijection only when $k=1$ and $k=2$ [Eli07].

Our hope would be that looking at *k-triangulations* as complexes of *k-stars* might perhaps be used to give a general explicit bijection between *k-triangulations* and Dyck *k-paths*. Observe that the number $n-2k$ of *k-stars* equals the semi-length of the Dyck *k-paths* we need to construct. Hence, the idea would be to use each *k-star* to represent one pair of steps in each path.

**Multi-associahedron.** Let $\Delta_{n,k}$ be the simplicial complex of all subsets of *k-relevant edges* of $E_n$ that do not contain any (*k* + 1)-crossing. Facets and ridges in $\Delta_{n,k}$ are *k-triangulations* of the *n*-gon and flips between them. Corollary 11 proves that $\Delta_{n,k}$ is pure, and Corollary 14 suggests that it could be a sphere; this was proved in [Jon03, Jon05]. But it remains a main open question to know whether $\Delta_{n,k}$ is polytopal. That is, whether it is the boundary complex of a polytope.

In our opinion, *k-stars* are a promising tool to answer this question: first because they give a better understanding of flips in *k-triangulations* and some constructions of the associahedron are based on understanding flips; but moreover because one of the most natural ways of constructing the associahedron is as a secondary polytope, which obviously uses triangles [BFS90].
**Rigidity.** A triangulation of a convex $n$-gon is a *minimally rigid* graph in the plane. That is to say, any continuous movement of its vertices that preserves all edge lengths extends to an isometry of the plane, and the triangulation is a minimal graph for this property. Moreover, it is generically so, meaning that the same is true for all embeddings of the same graph with sufficiently generic choice of positions for the vertices (see [Gra01] for an introduction to rigidity theory).

Note that Corollary 11 implies that $k$-triangulations have the $2k$-Laman property: $|E| = 2k|V| - \binom{2k+1}{2}$, and for any subgraph, $|E'| \le 2k|V'| - \binom{2k+1}{2}$. This property is a necessary condition for generic minimal rigidity, which puts forward the conjecture that every $k$-triangulation is generically minimally rigid in dimension $2k$. We have proved this conjecture for $k=2$.

## References

[BFS90] L. J. Billera, P. Filliman, and B. Sturmfels. Constructions and complexity of secondary polytopes. *Adv. Math.*, 83(2):155–179, 1990.

[CP92] V. Capoyleas and J. Pach. A Turán-type theorem on chords of a convex polygon. *J. Combin. Theory Ser. B*, 56(1):9–15, 1992.

[DCV86] M. Desainte-Catherine and G. Viennot. Enumeration of certain Young tableaux with bounded height. In *Combinatoire énumérative (Montreal, Que., 1985/Quebec, Que., 1985)*, volume 1234 of *Lecture Notes in Math.*, pages 58–67. Springer, 1986.

[DGJM07] A. Dress, S. Grünewald, J. Jonsson, and V. Moulton. The simplicial complex $\Delta_{n,k}$ of $k$-compatible line arrangements in the hyperbolic plane. *Preprint*, 2007.

[DKM02] A. W. M. Dress, J. H. Koolen, and V. Moulton. On line arrangements in the hyperbolic plane. *European J. Combin.*, 23(5):549–557, 2002.

[Eli07] S. Elizalde. A bijection between 2-triangulations and pairs of non-crossing dyck paths. *J. Combin. Theory Ser. A*, 114(8):1481–1503, 2007.

[Gra01] J. E. Graver. *Counting on frameworks*, volume 25 of *The Dolciani Mathematical Expositions*. The Mathematical Association of America, 2001.

[Jon03] J. Jonsson. Generalized triangulations of the $n$-gon. *Unpublished manuscript*, 2003. An abstract was included in: "Topological and Geometric Combinatorics, April 6th - April 12th, 2003", Mathematisches Forschungsinstitut Oberwolfach, Report No. 16/2003,

[Jon05] J. Jonsson. Generalized triangulations and diagonal-free subsets of stack polyominoes. *J. Combin. Theory Ser. A*, 112(1):117–142, 2005.

[Nak00] T. Nakamigawa. A generalization of diagonal flips in a convex polygon. *Theoret. Comput. Sci.*, 235(2):271–282, 2000.

[PS07] V. Pilaud and F. Santos. Multi-triangulations as complexes of star-polygons. *Preprint* [arXiv:math.CO/0706.3121v2], accepted in *Discrete Comput. Geom.*, 2007.

[STT88] D. D. Sleator, R. E. Tarjan, and W. P. Thurston. Rotation distance, triangulations, and hyperbolic geometry. *J. Amer. Math. Soc.*, 1(3):647–681, 1988.