Enumerating planar stuffed maps as hypertrees of mobiles

Abstract

A planar stuffed map is an embedding of a graph into the 2-sphere $S^2$, considered up to orientation-preserving homeomorphisms, such that every connected component of the complement is homeomorphic to a sphere with one or more boundary components. This generalizes planar maps, for which every component of the complement is a disc. We construct a bijection between bipartite planar stuffed maps and collections of integer-labelled trees connected by hyperedges whose underlying hypergraph is a hypertree; we call these objects hypermobiles. The bijection directly generalizes the Bouttier–Di Francesco–Guitter bijection between bipartite planar maps and mobiles. We also show that the generating functions of hypermobiles satisfy an algebraic equation, generalizing the ordinary planar-map case, and a new functional equation. As an example, we explicitly enumerate a class of stuffed quadrangulations.