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

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 Bender and Canfield in [BC94] 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 Arquès ([Arq87]) of the generating function of planar maps with respect to vertices and faces.