Number of Crossing-Free Geometric Graphs vs. Triangulations

We show that there is a constant α>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 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 cn⋅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 M2⋅tr(P), or c=2M/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 n8 factor to the bound for triangulations; we slightly decrease this bound to O(n343.11).