Suppose that a planar graph $\Gamma$ is quasi-isometric to the Euclidean plane. Is it true that the growth function $g(r)$ of $\Gamma$ with respect to any vertex $o$ (that is $g(r)$ is the number of vertices at path distance $\le r$ from $o$) is quadratic? The statement is not true for non-planar graph (take the square grid and replace every vertex by a large full graph).
$\begingroup$
$\endgroup$
8
-
1$\begingroup$ I'm sure you can get a counterexample by taking the square grid, and attaching to each vertex randomly one of two distinct finite planar graphs having two distinct numbers of vertices. $\endgroup$– Lee MosherCommented Dec 16, 2016 at 17:38
-
$\begingroup$ You mean an graph embedded in the plane? $\endgroup$– Andreas ThomCommented Dec 16, 2016 at 17:38
-
4$\begingroup$ There are also trivial planar counterexamples (from the standard graph $\mathbf{Z}^2$, add the vertices $(k/3^n,n):1\le k\le 2^n$ and join them to $(0,n-1)$ by a straight edge). So it sounds hopeless unless you require bounded valency. $\endgroup$– YCorCommented Dec 16, 2016 at 20:16
-
1$\begingroup$ Mark, there are no vertices of degree 1 or 2 in my example (the edge between $(0,n)$ and $(1,n)$ has to be replaced by $2^n$ horizontal edges. $\endgroup$– YCorCommented Dec 16, 2016 at 21:36
-
1$\begingroup$ If you want to do only lower bound for degree, then 6 seems to be enough (and trivial) and for 5 there are counterexamples. $\endgroup$– Anton PetruninCommented Dec 17, 2016 at 3:14
|
Show 3 more comments