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!

  • $\begingroup$ 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. $\endgroup$
    – plop
    Commented Mar 24, 2021 at 13:21
  • $\begingroup$ 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 $\endgroup$
    – nir shahar
    Commented Mar 24, 2021 at 13:26
  • $\begingroup$ 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. $\endgroup$
    – user114966
    Commented Mar 24, 2021 at 23:13
  • $\begingroup$ 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 $\endgroup$
    – nir shahar
    Commented Mar 24, 2021 at 23:34
  • $\begingroup$ 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)}$. $\endgroup$
    – user114966
    Commented Mar 24, 2021 at 23:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.