Computing permanents via determinants for some classes of sparse matrices (Q852624)

\textit{B. Codenotti} and \textit{G. Resta} [Linear Algebra Appl. 355, No. 1--3, 15--34 (2002; Zbl 1017.65044)] have given a formula expressing the permanent of a circulant \((0,1)\) matrix with only 3 or 4 ones per row as the sum of only few determinants. The analysis is based on the bipartite graph that is associated with the given matrix. Only few determinants need to be computed if the graph is embeddable in a surface of low genus (1 or 2). It is shown in this paper that the latter property can hold for certain \((0,1)\) matrices that may not be circulant.