Günter Rote:

The number of spanning trees in a planar graph

In: Oberwolfach Reports, 2, European Mathematical Society - Publishing House, 2005, pp. 969–973. doi:10.4171/OWR/2005/17


A planar graph with n vertices has at most 5.333...n spanning trees. If it has no triangle, it has at most 3.53n spanning trees. If it is 3-connected planar and without a face cycle of length three or four it has at most 2.848n spanning trees. These bound are obtained with a probabilistic method. They are applied to the construction of 3-dimensional polytopes with a given combinatorial structure and with small integral vertex coordinates. 

  PostScript file (gzipped)   pdf file
other papers about this subject
Last update: April 29, 2015.