A bijection for triangulations of a polygon with interior points and multiple edges - Département d'informatique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2003

A bijection for triangulations of a polygon with interior points and multiple edges

Résumé

Loopless triangulations of a polygon with $k$ vertices in $k+2n$ triangles (with interior points and possibly multiple edges) were enumerated by Mullin in 1965, using generating functions and calculations with the quadratic method. In this article we propose a simple bijective interpretation of Mullin's formula. The argument rests on the method of conjugacy classes of trees, a variation of the cycle lemma designed for planar maps. In the much easier case of loopless triangulations of the sphere ($k=3$), we recover and prove correct an unpublished construction of the second author.

Dates et versions

hal-00159307 , version 1 (02-07-2007)

Identifiants

Citer

Dominique Poulalhon, Gilles Schaeffer. A bijection for triangulations of a polygon with interior points and multiple edges. Theoretical Computer Science, 2003, 307 (2), pp.385-401. ⟨10.1016/S0304-3975(03)00226-3⟩. ⟨hal-00159307⟩
259 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More