patternMinor
Number of planar graphs, given an embedding
Viewed 0 times
numbergraphsplanarembeddinggiven
Problem
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!
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!
Solution
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$.
Context
StackExchange Computer Science Q#136978, answer score: 3
Revisions (0)
No revisions yet.