On the number of spanning trees a planar graph can have

K. Buchin, A. Schulz

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

27 Citaten (Scopus)

Samenvatting

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).
Originele taal-2Engels
TitelAlgorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I)
RedacteurenM. Berg, de, U. Meyer
Plaats van productieBerlin
UitgeverijSpringer
Pagina's110-121
ISBN van geprinte versie978-3-642-15774-5
DOI's
StatusGepubliceerd - 2010

Publicatie series

NaamLecture Notes in Computer Science
Volume6346
ISSN van geprinte versie0302-9743

Vingerafdruk Duik in de onderzoeksthema's van 'On the number of spanning trees a planar graph can have'. Samen vormen ze een unieke vingerafdruk.

Citeer dit