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
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.