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= P1,P2 of partial Latin squares is called a Latin bitrade. The number of filled cells in P1 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 va??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.
|Pages (from-to)||193 - 197|
|Number of pages||5|
|Journal||Journal of Combinatorial Theory - Series A|
|Publication status||Published - 2008|