TY - JOUR

T1 - Planar Eulerian triangulations are equivalent to spherical Latin bitrades

AU - Cavenagh, Nicholas

AU - Lisonek, Petr

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WHS-4NT84K3-3&_user=10&_coverDate=01%2F31%2F2008&_rdoc=12&_fmt=high&_orig=browse&_srch=doc-

M3 - Article

VL - 115

SP - 193

EP - 197

JO - Journal of Combinatorial Theory - Series A

JF - Journal of Combinatorial Theory - Series A

SN - 0097-3165

IS - 1

ER -