Séminaire Lotharingien de Combinatoire, B61Ah (2010), 29 pp.
Nicolas Bonichon, Mireille Bousquet-Mélou and Éric Fusy
Baxter Permutations and Plane Bipolar Orientations
a simple bijection between Baxter permutations of size n
and plane bipolar orientations with n edges. This bijection
translates several classical parameters of permutations (number of
ascents, right-to-left maxima, left-to-right
minima ...) into natural parameters of plane bipolar orientations
(number of vertices, degree of the sink, degree of the
source ...), and has remarkable symmetry properties.
By specializing it to Baxter permutations avoiding the pattern 2413, we
obtain a bijection with non-separable planar maps.
A further specialization yields a bijection between permutations avoiding 2413 and
3142 and series-parallel maps.
Received: July 15, 2008.
Accepted: January 11, 2010.
Final Version: February 13, 2010.
The following versions are available: