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
    Mar 24 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
    Mar 24 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
    Mar 24 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
    Mar 24 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
    Mar 24 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.