3
$\begingroup$

I want to find an upper bound on the number of planar graphs with $n$ vertices, assuming that we are given some embedding for those vertices beforehand. In particular, Im interested in either showing for every embedding there is $2^{o(n\log(n))}$ planar graphs, or showing that there exists an embedding with $2^{\Omega(n\log(n))}$ different planar graphs.

I know that without fixing embedding there is $2^{\Theta(n\log(n))}$, but my question differs from it since we fix an embedding beforehand.

I believe that still there is an embedding with $2^{\Omega(n\log(n))}$, but I couldn't prove or disprove it. Here is an attempt I made to try and calculate the number of planar graphs for some embedding I believed would be "hard", but it didn't work out as expected.

Thanks in advance!

$\endgroup$
3
$\begingroup$

Pach and Wenger proved in their paper Embedding planar graphs at fixed vertex locations that if $p_1,\ldots,p_n$ are $n$ different points on the plane, then every planar graph on $n$ vertices $v_1,\ldots,v_n$ has a planar embedding in which $v_i$ is found at position $p_i$.

$\endgroup$
3
  • $\begingroup$ This sounds too good to be true... I would expect that there would be less planar graphs if we fix the embedding beforehand. But what you are saying is that this number is exactly the same. Right? $\endgroup$ – nir shahar Mar 23 at 10:13
  • $\begingroup$ That’s what Pach and Wenger are saying, to the best of my understanding. $\endgroup$ – Yuval Filmus Mar 23 at 12:05
  • $\begingroup$ Hmmm. If I understood correctly, they allow for edges to take any path. I didn't state it in the question, but im looking at graphs whose edges are linear segments (they connect with a direct line their two endpoints). Thanks! I will post another question with this added to it $\endgroup$ – nir shahar Mar 23 at 13:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.