We prove that any planar graph on n vertices has less than 5:2852n spanning trees.
Under the restriction that the planar graph is 3-connected and contains no triangle and no quadrilateral the number of its spanning trees is less than 2:7156n. As a consequence of the latter the grid size needed to realize a 3d polytope with integer coordinates can be bounded by O(147:7n). To bound the number of spanning trees, we consider the class of directed graphs obtained by taking one outgoing edge at each vertex of the original graph. We probabilistically analyze the dependencies between cycles occurring in these graphs. From this we derive a linear program with infinitely many variables that bounds the number of spanning trees in terms of the degree sequence of the graph.
We solve the dual program for a small number of constraints, and then show that the solution obtained also fulfills the remaining constraints.
|Number of pages||18|
|Publication status||Published - 2009|