For arbitrary graphs, just counting the number of domino tilings is \(\# P\) -complete, since it involves computing the permanent of the adjacency matrix. However, it is known from [1]} and [2]} that this can be simplified for planar graphs to polynomial time, and for \(m \times n\)  rectangles the following formula exists
\( \prod _{i=1}^{\lceil \frac{m}{2} \rceil }\prod _{j=1}^{\lceil \frac{n}{2} \rceil } \big ( 4 \cos ^2 \frac{\pi i}{m+1} + 4 \cos ^2 \frac{\pi j}{n+1} \big ). \) 
