A Generic Method for Bijections between Blossoming Trees and Planar Maps
A Generic Method for Bijections between Blossoming Trees and Planar Maps
复制标题
开花树和平面映射之间双射的通用方法
DOI：
--
复制
发表时间：
2013
影响因子：
0.7
通讯作者：
Dominique Poulalhon
中科院分区：
文献类型：
--
作者：
M. Albenque;Dominique Poulalhon
本文提出了平面地图与开花树之间的统一双射方案，其中开花树定义为地图的生成树，该生成树装饰有一些悬垂的半边，可以重建开花树的面。我们的方法通过放宽其应用条件来推广先前的Bernardi构造，从而包括环形映射，即嵌入平面的根面与外面不同的映射。
This article presents a unified bijective scheme between planar maps and blossoming trees, where a blossoming tree is defined as a spanning tree of the map decorated with some dangling half-edges that enable to reconstruct its faces. Our method generalizes a previous construction of Bernardi by loosening its conditions of applications so as to include annular maps, that is maps embedded in the plane with a root face different from the outer face.
The bijective construction presented here relies deeply on the theory of alpha-orientations introduced by Felsner, and in particular on the existence of minimal and accessible orientations. Since most of the families of maps can be characterized by such orientations, our generic bijective method is proved to capture as special cases all previously known bijections involving blossoming trees: for example Eulerian maps, m-Eulerian maps, non separable maps and simple triangulations and quadrangulations of a k-gon. Moreover, it also permits to obtain new bijective constructions for bipolar orientations and d-angulations of girth d of a k-gon.
As for applications, each specialization of the construction translates into enumerative by-products, either via a closed formula or via a recursive computational scheme. Besides, for every family of maps described in the paper, the construction can be implemented in linear time. It yields thus an effective way to encode and generate planar maps.
In a recent work, Bernardi and Fusy introduced another unified bijective scheme, we adopt here a different strategy which allows us to capture different bijections. These two approaches should be seen as two complementary ways of unifying bijections between planar maps and decorated trees.