Séminaire Lotharingien de Combinatoire, B61Ah (2010), 29 pp.
Nicolas Bonichon, Mireille Bousquet-Mélou and Éric Fusy
Baxter Permutations and Plane Bipolar Orientations
Abstract.
We present
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: