On the Number of Plane Geometric Graphs

• DOI: 10.1007/s00373-007-0704-5
• Publication Date: 2007-07-02T11:26:17Z
• Authors: Oswin Aichholzer; Thomas Hackl; Clemens Huemer; Ferran Hurtado; Hannes Krasser; Birgit Vogtenhuber
• Keywords: General position; Indifference graph; Cardinality (data modeling)

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 geometric graphs and connected plane geometric graphs as well as the number of cycle-free plane geometric 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 a unified proof that the cardinality of any family of acyclic graphs (for example spanning trees, forests, perfect matchings, spanning paths, and more) is minimized for point sets in convex position. In addition we construct a new maximizing configuration, the so-called double zig-zag chain. Most noteworthy this example bears Θ* $${{(\sqrt{72}\,}^n)}$$ = Θ*(8.4853n) triangulations (omitting polynomial factors), improving the previously known best maximizing examples.