Authors: Guillaume Chapuy ¹; Valentin Feray ²; Eric Fusy ³

• 1 Laboratoire d'informatique Algorithmique : Fondements et Applications
• 2 Laboratoire Bordelais de Recherche en Informatique
• 3 Laboratoire d'informatique de l'École polytechnique [Palaiseau] [LIX]

We consider unicellular maps, or polygon gluings, of fixed genus. In FPSAC '09 the first author gave a recursive bijection transforming unicellular maps into trees, explaining the presence of Catalan numbers in counting formulas for these objects. In this paper, we give another bijection that explicitly describes the ``recursive part'' of the first bijection. As a result we obtain a very simple description of unicellular maps as pairs made by a plane tree and a permutation-like structure. All the previously known formulas follow as an immediate corollary or easy exercise, thus giving a bijective proof for each of them, in a unified way. For some of these formulas, this is the first bijective proof, e.g. the Harer-Zagier recurrence formula, or the Lehman-Walsh/Goupil-Schaeffer formulas. Thanks to previous work of the second author this also leads us to a new expression for Stanley character polynomials, which evaluate irreducible characters of the symmetric group.