9-13 June 2013
Koper, Slovenia
UTC timezone
Home > Timetable > Contribution details
PDF | XML

An improved lower bound on the maximum number of non-crossing spanning trees

Presented by Clemens HUEMER
Type: Oral presentation
Track: Discrete and Computational Geometry

Content

We address the problem of counting geometric graphs on point sets. Using analytic combinatorics we show that the so-called double chain point configuration of $N$ points has $\Omega^*(12.31^N)$ non-crossing spanning trees and $\Omega^*(13.40^N)$ non-crossing forests. This improves the previous lower bounds on the maximum number of non-crossing spanning trees and of non-crossing forests among all sets of $N$ points in general position given by Dumitrescu, Schulz, Sheffer and T\'oth in 2011. A new upper bound of $O^*(22.12^N)$ for the number of non-crossing spanning trees of the double chain is also obtained.

Place

Location: Koper, Slovenia

Primary authors

  • Clemens HUEMER Universitat Politècnica de Catalunya, Barcelona-Tech
  • Anna DE MIER Universitat Politècnica de Catalunya, Barcelona-Tech
More