On the number of plane graphs
Oswin Aichholzer, Thomas Hackl, Birgit Vogtenhuber, Clemens Huemer, Ferrán Hurtado, Hannes Krasser · Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 · 2006
We investigate the number of plane geometric, i.e., straight-line, graphs, a set S of n points in the plane admits. We show that the number of plane graphs and connected plane graphs as well as the number of cycle-free plane graphs is minimized when S is in convex position. Moreover, these results hold for all these graphs with an arbitrary but fixed number of edges. Consequently, we provide simple proofs that the number of spanning trees, cycle-free graphs (forests), perfect matchings, and spanning paths is also minimized for point sets in convex position.In addition we construct a new extremal configuration, the so-called double zig-zag chain. Most noteworthy this example bears Θ*(√72n) = Θ*(8.4853n) triangulations and Θ*(41.1889n) plane graphs (omitting polynomial factors in both cases), improving the previously known best maximizing examples.