1
$\begingroup$

Does anybody know if there is any research on a lower bound on the number of (non-isomorphic) unlabeled planar graphs with maximum node degree $d$?

Alternatively, a lower bound on the number of all unlabeled planar graphs will also help if the proof could possibly be modified for graphs with bounded degree. There is, for example, a paper by Giménez and Noy on the asymptotic number of labeled planar graphs but it seems not too easy to understand and modify the proof to work for unlabeled planar graphs with bounded degree.

I'm not looking for the best bounds known. Something like $\Omega(2^{cn})$ for some $c>0$ (preferably with an easier proof than the best known result) would be sufficient (if it holds).

Paper mentioned before:

  • Giménez, Omer, and Marc Noy. "The number of planar graphs and properties of random planar graphs." International Conference on Analysis of Algorithms DMTCS proc. AD. Vol. 147. 2005.
Improve this question
$\endgroup$

3 Answers 3

Reset to default
4
$\begingroup$

As Emil points out, finding some exponential lower bound is easy even for highly restricted classes of graphs. If I calculated correctly, the number of non-isomorphic caterpillars with $n$ vertices and maximum degree $\Delta$ is $$ n^{O(1)} \eta_\Delta^{-n}$$ where $\eta_\Delta$ is the smallest zero of $x^\Delta-2x+1$. (A caterpillar is a tree consisting of a path with extra vertices adjacent to the path.)

By allowing more graphs, the constants can be bumped up a lot. In W. T. Tutte, A census of planar triangulations, Canad J Math 14 (1962), 21-38, it is shown that the number of 3-connected planar cubic graphs with $n$ vertices is $$ n^{O(1)} \bigl(256/27\bigr)^{n/2},$$ which is bigger than $3^n$.

Improve this answer
$\endgroup$
2
$\begingroup$

I believe one can get $2^{\Omega(n)}$ quite easily. For instance, for any $I\subseteq\{1,\dots,m\}$, let $G$ be the graph with vertex set $\{0,\dots,3m+2\}$ with edges $\{i,i+1\}$ for each $i\le 3m+1$, and $\{3i-2,3i\}$ for each $i\in I$. Putting $n=3m+3$, this makes $\Omega(2^{n/3})$ nonisomorphic connected planar graphs of order $n$ and degree $3$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Take a circular ladder made of two concentric $n/2$-cycles and $n/2$ steps (also known as an $n/2$-prism). Now delete some subset of the steps. It needs some proving but $\Omega(2^{n/2}/n)$ non-isomorphic graphs of maximum degree 3 will result. $\endgroup$
    – Brendan McKay
    Commented Sep 11, 2014 at 1:50
  • $\begingroup$ What is the reason for the downvote? $\endgroup$
    – Emil Jeřábek
    Commented Sep 14, 2014 at 9:34
1
$\begingroup$

In the paper "Assymptotic study of subcritical graph classes" (see link here) the authors obtains the exponential growth for unlabelled series-parallel graphs, which is subfamily of unlabelled planar graphs.

The proof is technical and based on cycle index sums. If you want something easier, you can always go for the Pólya trees (which is known for a long time), but in this case the constant growth will be smaller.

Concerning the problem of unlabelled planar graphs: the combinatorial strategy of Giménez and Noy is the good one, but one needs two main ingredients: to transform the equations into unlabelled ones (this is already understood), and get exact counting formulas for the number of 3-connected and unrooted planar maps. Here there is the main problem: is difficult to control all the possible symmetries.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .