N. Cavenagh, P. Lisonek,
Planar Eulerian triangulations are equivalent to spherical Latin bitrades.
Journal of Combinatorial Theory Ser. A 115 (2008), 193-197.

Given a pair of latin squares, we may remove from both squares those cells that contain the same symbol in corresponding positions. The resulting pair $T=\{P_1,P_2\}$ of partial latin squares is called a latin bitrade. The number of filled cells in $P_1$ is called the size of $T$. There are at least two natural ways to define the genus of a latin bitrade; the bitrades of genus 0 are called spherical. We construct a simple bijection between the isomorphism classes of planar Eulerian triangulations on $v$ vertices and the main classes of spherical latin bitrades of size $v-2$. Since there exists a fast algorithm (due to Batagelj, Brinkmann and McKay) for generating planar Eulerian triangulations up to isomorphism, our result implies that also spherical latin bitrades can be generated very efficiently.

Back to the index of publications