A new combinatorial identity for unicellular maps, via a direct bijective approach

A unicellular map, or one-face map, is a graph embedded in an orientable surface such that its complement is a topological disk. In this paper, we give a new viewpoint to the structure of these objects, by describing a decomposition of any unicellular map into a unicellular map of smaller genus. This gives a new combinatorial identity for the number ϵg(n) of unicellular maps with n edges and genus g. Unlike the Harer-Zagier recurrence formula, this identity is recursive in only one parameter (the genus).Iterating the construction gives an explicit bijection between unicellular maps and plane trees with distinguished vertices, which gives a combinatorial explanation (and proof) of the fact that ϵg(n) is the product of the n-th Catalan number by a polynomial in n. The combinatorial interpretation also gives a new and simple formula for this polynomial. Variants of the problem are considered, like bipartite unicellular maps, or unicellular maps with only cubic vertices.