5
$\begingroup$

What are the best known bounds on the number of non-isomorphic (unlabelled) planar graphs on $n$ vertices? Is there a simple proof that this number is at most exponential in $n$?

$\endgroup$
12
$\begingroup$

Simple proof? Sort of. Let $t(n)$ be the number of plane triangulations with $n$ vertices. Tutte found an explicit formula for $t(n)$, implying that $t(n)\sim c n^\alpha \gamma^n$, where $\gamma=256/27$. From here, the number $a(n)$ of non-isomorphic planar graphs is at most $2^{3n-6}t(n)$, also exponential. There is an elegant bijective proof of Tutte's formula by Poulalhon and Schaeffer, but I wouldn't call it "simple".

For an exponential upper bound, there is a way to simplify the Poulalhon-Schaeffer proof. Take a rooted plane triangulation $G$ (rooted means a vertex and an adjacent edge are labeled). Denote by $T$ the depth-first search tree which is a planar tree with $n$ vertices and the same root. The number of such trees is the Catalan number $C_{n-1}$. Now we need to triangulate the complement of $T$ in the plane, which is bounded by the number of triangulations of $2(n-1)$-gon (twice the number of edges of $T$). The latter is equal to $C_{2n-4}$. Since $C_k<4^k$, putting these together gives an upper bound $$a(n) < 2^{3n} \cdot 4^n \cdot 4^{2n} = 2^{9n}.$$ One can easily get rid of the $2^{3n}$ term by realizing that you are overcounting, but that requires a bit of an explanation and a tiny bit more background.

$\endgroup$
1
$\begingroup$

The number is at most exponential, as you can see from this nice survey. (By Eric Fusy), as he also mentions, getting the precise asymptotics is nontrival (also, he talks about labelled graphs, but a general graph has trivial automorphism group, so you just divide by $n!.$

$\endgroup$
  • $\begingroup$ Thanks for the link Igor! However, I also don't see an easy way to see that a typical unlabelled graph admits n! distinct labellings. Also, I was hoping that there might be a simple proof of a weaker exponential bound... $\endgroup$ – Rob Dec 19 '13 at 21:57
  • 2
    $\begingroup$ I don't have the details at my fingertips, but generally what happens in planar graph classes is that any possible fixed induced subgraph occurs in a large random planar graph a linear number of times. Wormald and others proved variations of this. It implies that the typical planar graph has exponentially many (abstract) automorphisms. However, there is a critical distinction between abstract isomorphism and embedding-preserving isomorphism that muddies the water here. $\endgroup$ – Brendan McKay Dec 19 '13 at 22:20

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.