On the number of spanning trees a planar graph can have

DOI10.1007/978-3-642-15775-2_10MaRDI QIDQ3586455zbMATH OpenOpenAlexFDO

Authors Kevin Buchin, André Schulz

Publication date 6 September 2010

Published in Algorithms – ESA 2010 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0912.0712

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30) Analysis of algorithms and problem complexity (68Q25)

Abstract: We prove that any planar graph on $n$ vertices has less than $O(5.2852^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^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)$. 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^n)$, the number of plane spanning trees on a set of $n$ points in the plane is bounded by $O(158.6^n)$, and the number of plane cycle-free graphs on a set of $n$ points in the plane is bounded by $O(194.7^n)$.

Recommendations

• The number of spanning trees of a family of plane graph
• Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
• Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
• scientific article; zbMATH DE number 1107718

Cited in

(18)

• Invulnerability of planar two-tree networks
• On numbers of pseudo-triangulations
• Skyscraper polytopes and realizations of plane triangulations
• The number of spanning trees of plane graphs with reflective symmetry
• Growth rates of groups associated with face 2-coloured triangulations and directed Eulerian digraphs on the sphere
• Configurations of non-crossing rays and related problems
• Formulas for the number of spanning trees in a maximal planar map
• Counting carambolas
• Realizing planar graphs as convex polytopes
• scientific article; zbMATH DE number 4079455 (Why is no real title available?)
• scientific article; zbMATH DE number 844159 (Why is no real title available?)
• Plane Spanning Trees in Edge-Colored Simple Drawings of $$K_{n}$$
• Spanning tree bounds for grid graphs
• Small grid embeddings of 3-polytopes
• Robust network formation with biological applications
• A duality transform for constructing small grid embeddings of 3d polytopes
• Numerical approach to centrality of optimal transportation networks
• Geometric bounds for spanning tree entropy of planar lattice graphs

This page was built for publication: On the number of spanning trees a planar graph can have

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586455)