Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees
The electronic journal of combinatorics, Tome 4 (1997) no. 1
Abstract: 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 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 of the generating function of planar maps with respect to vertices and faces.
@article{10_37236_1305,
author = {Gilles Schaeffer},
title = {Bijective census and random generation of {Eulerian} planar maps with prescribed vertex degrees},
journal = {The electronic journal of combinatorics},
year = {1997},
volume = {4},
number = {1},
doi = {10.37236/1305},
zbl = {0885.05076},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1305/}
}
Gilles Schaeffer. Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees. The electronic journal of combinatorics, Tome 4 (1997) no. 1. doi: 10.37236/1305
Cité par Sources :