# 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.

• 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.
• 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.
• 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)}$.