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

Dominique Poulalhon 1 Gilles Schaeffer 2
2 ADAGE - Applying discrete algorithms to genomics
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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 construction of Mullin's formula. The argument rests on conjugation 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. || Les triangulations sans boucles d'un polygone à $k$ côtés en $k+2n$ triangles (avec des points intérieurs et éventuellement des arêtes multiples) ont été énumérées par Mullin en 1965, à l'aide de séries génératrices et de la méthode quadratique. Dans cet
Type de document :
Rapport
[Intern report] A02-R-362 || poulalhon02c, 2002, 21 p
Liste complète des métadonnées

https://hal.inria.fr/inria-00101067
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:55:20
Dernière modification le : jeudi 10 mai 2018 - 02:06:34

Identifiants

  • HAL Id : inria-00101067, version 1

Citation

Dominique Poulalhon, Gilles Schaeffer. A bijection for triangulations of a polygon with interior points and multiple edges. [Intern report] A02-R-362 || poulalhon02c, 2002, 21 p. 〈inria-00101067〉

Partager

Métriques

Consultations de la notice

231