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
Abstract
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.
Last update: April 29, 2015.