A NEW APPROACH TO SOLVING 3 COMBINATORIAL ENUMERATION PROBLEMS ON PLANAR GRAPHS

The purpose of this paper is to show how the technique of delta-wye gr aph reduction provides an alternative method for solving three enumera tive function evaluation problems on planar graphs. In particular, it is shown how to compute the number of spanning trees and perfect match ings, and how to evaluate energy in the Ising ''spin glass'' model of statistical mechanics. These alternative algorithms require O(n(2)) ar ithmetic operations on an n-vertex planar graph, and are relatively ea sy to implement.