Bounding the number of plane graphs

O. Aichholzer, T. Hackl, C. Huemer, F. Hurtado, H. Krasser, and B. Vogtenhuber

Abstract:

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 $\Theta^*(\sqrt{72}\,^n)$ = $\Theta^*(8.4853^n)$ triangulations and $\Theta^*(41.1889^n)$ plane graphs (omitting polynomial factors in both cases), improving the previously known best maximizing examples.

Reference: O. Aichholzer, T. Hackl, C. Huemer, F. Hurtado, H. Krasser, and B. Vogtenhuber. Bounding the number of plane graphs. In Proc. $15^{th}$ Annual Fall Workshop on Computational Geometry and Visualization, pages 31-32, Philadelphia, Pennsylvania, USA, 2005.