# Counting spanning trees of a planar graph

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.

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
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