"On the Number of Planar Geometric Graphs"

We investigate the number of (different embeddings of) planar geometric, i.e., straight-line, graphs a set S of n points in the plane admits. We show that the number of planar graphs and connected planar graphs as well as the number of cycle-free planar graphs is minimized when S is in convex position. Moreover these results hold for any fixed number of edges of these graphs.

Consequently we provide simple proofs that the number of spanning trees, forests, perfect matchings, and spanning paths is also minimized for point sets in convex position.

Moreover we construct a new extremal configuration, the so-called double zig-zag chain. Most noteworthy this example bears asymptotically 8.48^n triangulations and 41.19^n planar graphs (omiting polynomial factors), improving the previously known best bounds.