Number of Crossing-Free Geometric Graphs vs.

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 (12 + α)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 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 2M · 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 8n factor to the bound for triangulations; we slightly decrease this bound to O(343.11n)