How many planar graphs with $n$ points at fixed locations and line-like edges?

42 Views Asked by At

A "geometrical" planar graph, is a graph whose vertices are two-dimentional points, and the edges are straight segments connecting them.

My question is: how can we calculate $T_n:=\max\{ \text{#geometrical planar graphs with $S$ as vertices}\mid S\subseteq\mathbb{R}^2,|S|=n \}$? A lower or an upper bound (in terms of big-O and omega) on $\log(T_n)$ would suffice for me as well.

I found a similar question here, regarding the number of simple polygons. However, unlike polygons, "geometrical" planar graphs don't necessarily have to be a closed shape.

I also posted this question here, in the computer science stack exchange (and didn't get an answer yet), but I think it also fits the mathematics stack exchange - so I will post it here as well (sorry for cross-posting)

Thanks in advance!