Number of Crossing-Free Geometric Graphs vs. Triangulations

We show that there is a constant $\alpha >0$ such that, for any set P of n⩾ 5 points in general position in the plane, a crossing-free geometric graph on P that is chosen uniformly at random contains, in expectation, at least $(\frac{1}{2}+\alpha )M$ edges, where M denotes the number of edges in any triangulation of P. From this we derive (to our knowledge) the first non-trivial upper bound of the form $c^n\cdot \mathsf{tr}(P)$ on the number of crossing-free geometric graphs on P; that is, at most a fixed exponential in n times the number of triangulations of P. (The trivial upper bound of $2^M\cdot \mathsf{tr}(P)$, or $c=2^{M/n}$, follows by taking subsets of edges of each triangulation.) If the convex hull of P is triangular, then $M=3n-6$, and we obtain $c<7.98$.Upper bounds for the number of crossing-free geometric graphs on planar point sets have so far applied the trivial $8^n$ factor to the bound for triangulations; we slightly decrease this bound to $O({343.11}^n)$.