Counting over non-planar graphs

In a framework at the interface between statistical physics and computational complexity, we discuss the extension of the Pfaffian formalism for the evaluation of the Ising partition function or of the weighted matching polynomial over planar lattices to the general case of non-planar graphs. The combinatorial features of the method acquire a simple topological character independent of the local details of the lattices. As a by product, we also give a simple formula for the evaluation of the permanent of 0-1 matrices in terms of determinants. (C) 2001 Elsevier Science B.V. All rights reserved.