Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees (Q1378513)

Summary: We give a bijection between Eulerian planar maps with prescribed vertex degrees, and some plane trees that we call balanced Eulerian trees. To enumerate the latter, we introduce conjugation classes of planted plane trees. In particular the result answers a question of \textit{E. A. Bender} and \textit{E. R. Canfield} [SIAM J. Discrete Math. 7, No. 1, 9-15 (1994; Zbl 0794.05048)] and allows uniform random generation of Eulerian planar maps with restricted vertex degrees. Using a well-known correspondence between \(4\)-regular planar maps with \(n\) vertices and planar maps with \(n\) edges we obtain an algorithm to generate uniformly such maps with complexity \(O(n)\). Our bijection is also refined to give a combinatorial interpretation of a parameterization of \textit{D. Arquès} [J. Comb. Theory, Ser. B 43, 253-274 (1987; Zbl 0628.05040)] of the generating function of planar maps with respect to vertices and faces.