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.



Counting spanning trees of a planar graph
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](https://en.wikipedia.org/wiki/Planar_separator_theorem) (see also [nested dissection](https://en.wikipedia.org/wiki/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](https://www.sciencedirect.com/science/article/pii/0166218X95E01113) Discrete Appl. Math., 60 (1995), pp. 119-129
> 
> 
> 


