Planar Eulerian triangulations are equivalent to spherical Latin bitrades

Nicholas Cavenagh, Petr Lisonek

Research output: Contribution to journalArticleResearchpeer-review

11 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)193 - 197
Number of pages5
JournalJournal of Combinatorial Theory - Series A
Volume115
Issue number1
Publication statusPublished - 2008

Cite this