Counting spanning trees of a planar graph

Question

I know through Kirchoff's Theorem, one can calculate the number of spanning trees via the determinant of a Laplacian. This has complexity $O(N^{2.373}$). I was wondering if anyone was aware of a method which computes this faster, at least for planar graphs.

Answer 1

The determinant of matrices whose support corresponds to incidence matrices of planar graphs (this includes the Laplacian matrix of a planar graph, or more precisely its cofactors) can be calculated in $O(n^{1.5})$ with the algorithm given in

R.J. Lipton, D. Rose, R.E. Tarjan Generalized nested dissection SIAM J. Numer. Anal., 16 (1979), pp. 346-358

which uses the planar separator theorem (see also nested dissection).

Another algorithm that runs in $O(n^2)$ but sometimes more efficient to implement is the one based on delta-wye graph reduction (a set of combinatorial substitution rules on the graph) given in

C.J. Colbourn, J.S. Provan, D. Vertigan A new approach to solving three combinatorial enumeration problems on planar graphs Discrete Appl. Math., 60 (1995), pp. 119-129