Bijective counting of plane bipolar orientations and Schnyder woods

Abstract

A bijection $\Phi$ is presented between plane bipolar orientations with prescribed numbers of vertices and faces, and non-intersecting triples of upright lattice paths with prescribed extremities. This yields a combinatorial proof of the following formula due to R. Baxter for the number ${\Theta }_{ij}$ of plane bipolar orientations with $i$ non-polar vertices and $j$ inner faces: ${\Theta }_{ij}=2\frac{(i+j)!(i+j+1)!(i+j+2)!}{i!(i+1)!(i+2)!j!(j+1)!(j+2)!}$. In addition, it is shown that $\Phi$ specializes into the bijection of Bernardi and Bonichon between Schnyder woods and non-crossing pairs of Dyck words.

An extended abstract describing the bijection without proofs has appeared in the proceedings of Eurocomb'07

Cited by in corpus (1)

• New bijective links on planar maps via orientations