HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Number of planar graphs, given an embedding

Submitted by: @import:stackexchange-cs··
0
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!

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.