# Number of planar graphs with linear edges, given a fixed embedding

Suppose we are given a set of $$n$$ points on the plane. How many different planar graphs can we form on those $$n$$ vertices, assuming that each edge must form a straight line between the two vertices it connects?

I'm interested in either showing for every set of points there are $$2^{o(n\log(n))}$$ planar graphs; or showing that there exists a set of points with $$2^{\Omega(n\log(n))}$$ different planar graphs.

I recently asked a similar question without the constraints that the edges form a straight line, and the answer I got directly utilizes this fact. I didn't specify this in the previous question, but I am actually interested only in graphs with those constraints. So, if anyone knows where I can find material about the number of such graphs, I would be glad to know about it as well.

Thanks in advance!

• The number of planar straight line graphs (PSLGs) for $n$ colinear points is $2^{n-1}$ because we can only put edges between consecutive vertices. So, each PSLG for these points is a choice of a subset of the $n-1$ spaces between the $n$ vertices. Of course, here I am counting embedded graphs. It is not clear if you want to count graphs up to isomorphism or not.
– plop
Commented Mar 24, 2021 at 13:21
• Thats right. However there might be a set of non-colinear points with more PSLGs. Im looking to either give an upper bound for every set of points, or find a set of points with a lot more PSLGs Commented Mar 24, 2021 at 13:26
• If I understood correctly, Counting Triangulations of Planar Point Sets answers your question: "maximal number of triangulations that a planar set of n points can have ... is at most $30^n$" and "Given a set $S$ of points in the plane, a triangulation of $S$ is a maximal planar graph on $S$". Since each planar graph has $O(n)$ edges, this should give an $2^{O(n)}$ bound.
– user114966
Commented Mar 24, 2021 at 23:13
• So what you are saying @Dmitry, is that its enough to look at the number of maximal planar graphs? I don't really see how the number of planar graphs can be bounded above by the number of maximal planar graphs. The other way around is obvious (every maximal planar graph is a planar graph, but not vice versa), so I don't really understand how this would solve my question Commented Mar 24, 2021 at 23:34
• Since each planar graph is a subset (in terms of edges) of some maximal planar graph, the number of planar graphs is at most $(\text{the number of maximal planar graphs}) \times (2^{\text{the maximum number of edges in a planar graph}})$, and both terms are $2^{O(n)}$.
– user114966
Commented Mar 24, 2021 at 23:37