Domino Tilings of 2 x n Grids (or Perfect Matchings of Grid Graphs) on Surfaces

It is well known that the number of edge-labeled perfect matchings of a 2 x n planar grid graph is the (n + 1)st Fibonacci number. The number of edge-labeled perfect matchings of grid graphs on surfaces has been computed using Pfaffians, matching polynomials, and generating functions. Here we present an elegant and elementary approach to enumerating edge-labeled perfect matchings of 2 x n grid graphs on surfaces representable by opposite-edge-identified quadrilaterals. For simplicity in description, we give proofs using the language of tilings of grids.