@inproceedings{e94511705f32453ab853bf0ad71c62bb,
title = "On the number of spanning trees a planar graph can have",
abstract = "We prove that any planar graph on n vertices has less than O(5.2852\textasciicircum{}n) 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 O(2.7156\textasciicircum{}n). As a consequence of the latter the grid size needed to realize a 3d polytope with integer coordinates can be bounded by O(147.7 n\textasciicircum{}). Our observations imply improved upper bounds for related quantities: the number of cycle-free graphs in a planar graph is bounded by O(6.4884\textasciicircum{}n), the number of plane spanning trees on a set of n points in the plane is bounded by O(158.6\textasciicircum{}n), and the number of plane cycle-free graphs on a set of n points in the plane is bounded by O(194.7\textasciicircum{}n).",
author = "K. Buchin and A. Schulz",
year = "2010",
doi = "10.1007/978-3-642-15775-2\_10",
language = "English",
isbn = "978-3-642-15774-5",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "110--121",
editor = "\{Berg, de\}, M. and U. Meyer",
booktitle = "Algorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I)",
address = "Germany",
}