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: