A Bijection Between Non-Separable Planar Maps and Fighting Fish

Abstract

The class of fighting fish is a recently introduced model of branching surfaces constructed by gluing square cells in a directed way, that generalizes the standard combinatorial class of parallelogram polyominoes. Fighting fish are enumerated with respect to their half-perimeter by the sequence $\frac{2}{(n+1)(2n+1)} \binom{3n}{n}$, also known for counting non-separable rooted planar maps w.r.t the number of edges. Another common feature of these two combinatorial classes is that fighting fish can be seen as particular excursions on the square lattice confined to the quarter plane, while excursions on the quarter plane encode tree-rooted planar maps via Mullin's encoding.

We build on this point of view and on recursive decompositions of fish and maps to show that fighting fish can be identified with the Lehman-Lenormand codes of non-separable rooted planar maps, which is obtained by endowing maps with their rightmost depth first search tree before applying Mullin's encoding. The resulting direct bijection yields a simple characterization of fighting fish as minimal non-separable excursions in the quarter plane.

We then also introduce a natural extension of fighting fish that we call generalized fighting fish and we follow again the same approach to show that they correspond to Lehman-Lenormand codes of (general) rooted planar maps.