Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees. | Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees Gilles Schaeffer LIX Ecole Polytechnique 91128 Palaiseau Cedex France Submitted May 7 1997 Accepted July 17 1997. 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 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 Arques Arq87 of the generating function of planar maps with respect to vertices and faces. Mathematical Subject Classification. Primary 05C30. 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 4 1997 R20 2 A planar map is a 2-cell decomposition of the oriented sphere into vertices 0-cells edges 1-cells faces 2-cells . The degree of a vertex is the number of edges incident to this vertex. Loops and multiple edges are allowed. Following . Tutte we consider here rooted maps . maps with an oriented edge called the root. The face which is on the right hand side of the root is called the exterior face of the map. Two rooted maps are isomorphic if there exists an orientation preserving homeomorphism of the sphere which maps cells of one map onto cells of the same type of the second in particular root edge on root edge and preserves incidences. We shall consider maps up to these isomorphisms. An Eulerian planar map is a map whose vertices have even degrees it is k-regular if all degrees are equal to k. Eulerian planar maps have been studied by . Tutte in Tut62 where
