A new approach to solving three combinatorial enumeration problems on planar graphs (Q1894355)

The authors consider six graph transformations: loop deletion, pendant edge deletion, parallel reduction, series reduction, \(Y\)-\(\Delta\) transformation and \(\Delta\)-\(Y\) transformation. A graph \(G\) is said to be \(\Delta Y\Delta\)-reducible if it can be reduced to a single edge by repeated applications of these transformations, in any sequence. Planar graphs are known to be \(\Delta Y\Delta\)-reducible; but so is the graph \(K_{3, 3}\). The class of \(\Delta Y\Delta\)-reducible graphs has not been characterized. \textit{T. A. Feo} and \textit{J. S. Provan} [Delta-wye transformations and the efficient reduction of two-terminal planar graphs, Oper. Res. 41, No. 3, 572-582 (1993; Zbl 0784.90095)] have obtained an \(O(n^2)\) algorithm to reduce a planar graph to an edge. In this paper the authors present a \(\Delta\)-\(Y\) reduction technique to solve combinatorial problems on planar graphs. The basic strategy is to associate a weight with each edge of the graph and express the combinatorial object to be evaluated as a function of these weights and study the effect of each of the six elementary transformations on this expression. Then, using the Feo-Provan algorithm, one has an \(O(n^2)\) algorithm to evaluate the expression. Complete details are given for three combinatorial problems: finding the number of spanning trees, the number of perfect matchings and evaluating the Ising partition function of a planar graph. The authors however observe that there are \(O(n^{1.5})\) algorithms for these problems using evaluation of determinants.