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 -