Number of unlabelled planar graphs

Question

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$?

Answer 1

Simple proof? Sort of.

Let $t(n)$ be the number of plane triangulations with $n$ vertices. Tutte [in ''A Census of Planar Triangulations,'' Canad. J. Math. 14 (1962), 21-38] 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.

Answer 2

There is a short proof of a stronger result by Norine, Seymour, Thomas, and Wollan that there is an exponential upper bound for every proper minor-closed class.

For every proper minor-closed class of graphs $\mathcal G$, there exists a constant $c$, such that for every integer $n$, there are at most $n! c^n$ graphs in $\mathcal G$ with vertex set $\{1, \dots, n\}$.

This is the labelled version of your question, but as Igor mentions, the typical graph has trivial automorphism group, so we can divide by $n!$.

The paper is entitled Proper minor-closed families are small and can be downloaded here or from Robin Thomas's webpage.

Answer 3

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!.$