On the Number of Spanning Trees a Planar Graph Can Have
On the Number of Spanning Trees a Planar Graph Can Have
复制标题
DOI：
10.1007/978-3-642-15775-2_10
复制
发表时间：
2009-12
期刊：
影响因子：
--
通讯作者：
K. Buchin;A. Schulz
中科院分区：
文献类型：
--
作者：
K. Buchin;A. Schulz
我们证明了任何顶点上的平面图的支撑树都小于O(5.2852n)。在平面图是3连通且不含三角形和四边形的约束下，其生成树的个数小于O(2.7156n)。作为后者的结果，实现具有整数坐标的3D多面体所需的网格大小可以由YO(147.7N)限定。我们的观察结果表明改进了相关数量的上界：平面图中无圈图的个数是BYO(6.4884n)，平面上点集上的平面支撑树的个数是BYO(158.6n)，平面上点集上的平面无圈图的个数是BYO(194.7n)。
We prove that any planar graph onnvertices has less thanO(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 thanO(2.7156n). As a consequence of the latter the grid size needed to realize a 3d polytope with integer coordinates can be bounded byO(147.7n). Our observations imply improved upper bounds for related quantities: the number of cycle-free graphs in a planar graph is bounded byO(6.4884n), the number of plane spanning trees on a set ofnpoints in the plane is bounded byO(158.6n), and the number of plane cycle-free graphs on a set ofnpoints in the plane is bounded byO(194.7n).