%\magnification=\magstep1
%\nopagenumbers
\font\bigrm=cmr17
\font\medrm=cmr12
\font\medbf=cmbx12
\def\sc{\it}
\def\sectioncount{\count11}
\sectioncount=0
\def\theoremcount{\count12}
\theoremcount=0
\def\lemmacount{\count13}
\lemmacount=0
\def\corollarycount{\count14}
\corollarycount=0
\def\exerciseno{\count15}
\exerciseno=0
\def\algorithmcount{\count16}
\algorithmcount=0
\def\figurecount{\count17}
\figurecount=0
\def\ex{\advance\exerciseno by 1
\item{\the\exerciseno.}
}
\def\section#1{\advance\sectioncount by 1
\medskip
{\par \noindent \bf\the\sectioncount.\enskip #1.}
\medskip
% \headline={{\sl #1\hfil\the\pageno}}
\theoremcount=0
\lemmacount=0
\corollarycount=0
}
\long\def\longtheorem#1{\advance\theoremcount by 1
\medskip
{\bf\noindent Theorem \the\sectioncount.\the\theoremcount\ :
\enskip}{\sl #1}
\medskip
}
\def\theorem#1{\advance\theoremcount by 1
\medskip
{\bf\noindent Theorem \the\sectioncount.\the\theoremcount\ :
\enskip}{\sl #1}
\medskip
}
\long\def\longlemma#1{\advance\lemmacount by 1
\medskip
{\bf\noindent Lemma \the\sectioncount.\the\lemmacount\ :
\enskip}{\sl #1}
\medskip
}
\def\lemma#1{\advance\lemmacount by 1
\medskip
{\bf\noindent Lemma \the\sectioncount.\the\lemmacount\ :
\enskip}{\sl #1}
\medskip
}
\long\def\longcorollary#1{\advance\corollarycount by 1
\medskip
{\bf\noindent Corollary \the\sectioncount.\the\corollarycount\ :
\enskip}{\sl #1}
\medskip
}
\def\corollary#1{\advance\corollarycount by 1
\medskip
{\bf\noindent Corollary \the\sectioncount.\the\corollarycount\ :
\enskip}{\sl #1}
\medskip
}
\long\def\longalgorithm#1{\advance\algorithmcount by 1
\medskip
{\bf\noindent Algorithm \the\sectioncount.\the\algorithmcount\ :
\enskip}{\sl #1}
\medskip
}
\def\algorithm#1{\advance\algorithmcount by 1
\medskip
{\bf\noindent Algorithm \the\sectioncount.\the\algorithmcount\ :
\enskip}{\sl #1}
\medskip
}
\long\def\figure#1#2#3{\advance\figurecount by 1
\vbox{
\vskip #1
\special{psfile="#2"}
\vskip .3true in
\centerline{Figure\ \the\figurecount.}
}
\medskip
\figurelabel{#3}
}
\def\proof{{\bf\noindent Proof}:\enskip}
%\def\qed{\hfill \vrule width4pt height8pt depth0pt}
\def\qed{\hfill\vbox to 4pt{\hrule\hbox to 4pt
{\vrule height 3pt depth 0pt \hfill \vrule}\vfill\hrule}
\medskip
}
\def\exerciselabel#1{\edef#1{\the\exerciseno}}
\def\theoremlabel#1{\edef#1{\the\sectioncount.\the\theoremcount}}
\def\lemmalabel#1{\edef#1{\the\sectioncount.\the\lemmacount}}
\def\corollarylabel#1{\edef#1{\the\sectioncount.\the\corollarycount}}
\def\algorithmlabel#1{\edef#1{\the\sectioncount.\the\algorithmcount}}
\def\figurelabel#1{\edef#1{\the\figurecount}}
\def\svs#1{{\sl S}_{#1}}
\def\dsvs#1{\dual{{\sl S}_{#1}}}
\def\dual#1{#1^*}
\def\comp#1{{\overline #1}}
\def\bibitem#1#2{
\vbox{
\smallskip\noindent \hangindent2\parindent \textindent{[#1]\ } #2}
}
\def\Z{{\bf Z}}
\def\T{\top}
\def\true{\top}
\def\false{\bot}
\def\F{\bot}
\def\iff{\leftrightarrow}
\def\underline#1{{\bf #1}}
\def\notequal{\not=}
\def\plusminus{\pm}
\def\circle{\circ}
\def\N{{\rm\bf N}}
\def\Z{{\rm\bf Z}}
\def\R{{\rm\bf R}}
\def\Q{{\rm\bf Q}}
\def\C{{\rm\bf C}}
\def\page{\vfill\eject}
\def\title#1{\centerline{\bigrm #1}\bigskip}
\def\author#1{\centerline{\bf #1}\par}
\def\department#1{\centerline{#1}\par}
\def\university#1{\centerline{#1}\par}
\def\address#1{\centerline{#1}\par}
\def\by#1#2#3#4{\author{#1}\department{#2}\university{#3}\address{#4}
\bigskip}
\def\({\left (}
\def\){\right )}
\def\[{\left [}
\def\]{\right ]}
\def\lf{\left\lfloor}
\def\rf{\right\rfloor}
\def\lc{\left\lceil}
\def\rc{\right\rceil}
\magnification=\magstep1
%\nopagenumbers
\font\bigrm=cmr17
\font\medbf=cmbx12
\def\sc{\it}
\def\margincomment#1{\hfill\rlap{\bf #1 }}
\def\sectioncount{\count11}
\sectioncount=0
\def\theoremcount{\count12}
\theoremcount=0
\def\lemmacount{\count13}
\lemmacount=0
\def\corollarycount{\count14}
\corollarycount=0
\def\figurecount{\count17}
\figurecount=0
\def\ex{\advance\exerciseno by 1
\item{\the\exerciseno.}
}
\def\section#1{\advance\sectioncount by 1
\medskip
{\par \noindent \bf\the\sectioncount.\enskip #1.}
\medskip
% \headline={{\sl #1\hfil\the\pageno}}
\theoremcount=0
\lemmacount=0
\corollarycount=0
}
\def\theorem#1{\advance\theoremcount by 1
\medskip
{\bf\noindent Theorem \the\sectioncount.\the\theoremcount\ :
\enskip}{\sl #1}
\medskip
}
\def\lemma#1{\advance\lemmacount by 1
\medskip
{\bf\noindent Lemma \the\sectioncount.\the\lemmacount\ :
\enskip}{\sl #1}
\medskip
}
\def\corollary#1{\advance\corollarycount by 1
\medskip
{\bf\noindent Corollary \the\sectioncount.\the\corollarycount\ :
\enskip}{\sl #1}
\medskip
}
\long\def\figure#1#2#3{\advance\figurecount by 1
\vbox{
\vskip #1
\special{psfile="#2"}
\vskip .3true in
\centerline{Figure\ \the\figurecount.}
}
\medskip
\figurelabel{#3}
}
\def\proof{{\bf\noindent Proof}:\enskip}
%\def\qed{\hfill \vrule width4pt height8pt depth0pt}
\def\qed{\hfill\vbox to 4pt{\hrule\hbox to 4pt
{\vrule height 3pt depth 0pt \hfill \vrule}\vfill\hrule}
\medskip
}
\def\theoremlabel#1{\edef#1{\the\sectioncount.\the\theoremcount}}
\def\lemmalabel#1{\edef#1{\the\sectioncount.\the\lemmacount}}
\def\corollarylabel#1{\edef#1{\the\sectioncount.\the\corollarycount}}
\def\figurelabel#1{\edef#1{\the\figurecount}}
\def\svs#1{{\sl S}_{#1}}
\def\dsvs#1{\dual{{\sl S}_{#1}}}
\def\dual#1{#1^*}
\def\comp#1{{\overline #1}}
\def\bibitem#1#2{
\vbox{
\smallskip\noindent \hangindent2\parindent \textindent{[#1]\ } #2}
}
\def\Z{{\bf Z}}
\def\T{\top}
\def\true{\top}
\def\false{\bot}
\def\F{\bot}
\def\iff{\leftrightarrow}
\def\underline#1{{\bf #1}}
\def\notequal{\not=}
\def\plusminus{\pm}
\def\circle{\circ}
\def\N{{\rm\bf N}}
\def\Z{{\rm\bf Z}}
\def\R{{\rm\bf R}}
\def\S{{\rm\bf S}}
\def\H{{\rm\bf H}}
\def\aut{{\rm aut}}
\def\({\left(}
\def\){\right)}
\def\page{\vfill\eject}
\def\title#1{\centerline{\bigrm #1}\bigskip}
\def\author#1{\centerline{\bf #1}\par}
\def\department#1{\centerline{#1}\par}
\def\university#1{\centerline{#1}\par}
\def\address#1{\centerline{#1}\par}
\def\by#1#2#3#4{\author{#1}\department{#2}\university{#3}\address{#4}
\bigskip}
\title{A Note on the Growth Rate of Planar Graphs}
\by{Neal Brand\footnote{$^1$}{\rm Supported by a University of North Texas Faculty Research Grant.}}
{Department of Mathematics}
{University of North Texas}
{Denton, TX 76203}
\centerline{and}\bigskip
\by{Margaret Morton\footnote{$^2$}{\rm Supported by a University of Auckland Research Committee Grant.}}
{Department of Mathematics}
{University of Auckland}
{Auckland, New Zealand}
\centerline{\bf Abstract}
If $\Gamma$ is a planar, locally finite, vertex transitive,
1-ended graph, then there is a particular `niceness' about the arrangement
of the regions incident to a vertex in $\Gamma$. Using this feature, it can
be shown that $\Gamma$ can be embedded in either the Euclidean plane or the
hyperbolic plane in such a way that every edge has the same length and every
angle in an n-cycle bounding a region has the same measure. Moreover, there is
a simple condition which tells whether $\Gamma$ is embedded in the Euclidean
plane or the hyperbolic plane. The geometry of these two planes is then
exploited to show that $\Gamma$ must have either quadratic growth or exponential
growth depending on which plane it is embedded in.
\section{Introduction}
The graphs considered in this paper are simple,
infinite, and planar.
The symbols $V(\Gamma)$, $E(\Gamma)$ and $\aut(\Gamma)$
will denote respectively,
the vertex set, the edge set, and the automorphism
group of $\Gamma$. All graphs will be
assumed to be {\it locally finite}; that is the degree
of every vertex is finite. The graph $\Gamma$ is said to be
{\it transitive} if
for
every pair of vertices $\{u,v\}$ in $\Gamma$ there
exists an automorphism $g$ of $\Gamma$ such that $g(u)=v$.
An {\it end} of a graph is an equivalence class of
one way infinite paths where two one way infinite
paths are equivalent if there are infinitely many
pairwise disjoint paths in the graph connecting them.
It is well known that every infinite, locally finite,
vertex transitive graph has either one, two or
infinitely many ends [4]. A useful alternative
condition for a 1-ended graph is that if any
finite subset $T$ of $V(\Gamma)$ is removed then
$\Gamma -T$ has just one infinite component.
\medskip
Let $\Gamma$ be a planar, locally finite, vertex
transitive, 1-ended graph. Since $\Gamma$ is
1-ended and vertex transitive each vertex has
degree at least 3 and $\Gamma$ is 3-connected [1].
By a generalization [3,4] of Whitney's result [5]
we know that when an infinite planar graph is
3-connected, the cyclic order of the edges incident
with each vertex when the graph is embedded in the
plane becomes an intrinsic property of the graph
and is the same for all planar embeddings. For a
biconnected planar graph we define a proper
embedding to be a planar embedding with the
property that the boundary of each face is
either an elementary circuit or a double ray.
Using a result of Halin [2] it follows that
every 1-ended, locally finite, planar graph
has a proper embedding. In Bonnington et al
[1] it is shown that if $\Gamma$ is a
locally finite, planar, 3-connected, transitive
graph, then it has no infinite faces in any
proper embedding.
\medskip
For the remainder of this paper we assume
that $\Gamma$ is a planar, locally finite,
vertex transitive, 1-ended graph. Furthermore, we assume $\Gamma$ is
embedded in the plane and sometimes abuse notation by identifying
vertices in $\Gamma$ with their images in the plane. Suppose
that each vertex in $\Gamma$ has degree $k\ge 3$
and that the edges
incident to a particular vertex $v_0$ in
$\Gamma$, given in counterclockwise order,
are
$e_1, \dots, e_k$ where $e_i=\{v_0, v_i \},
1 \le i \le k$. Each consecutive pair of
edges incident to $v_0$ form part of a cycle
enclosing a region incident to $v_0$. Let
$R_i$ denote the closed region bounded by the
cycle of $n_i$ edges which includes $e_i$
and $e_{i+1}$, $1 \le i \le k-1$, and
$R_k$ denote the closed region bounded by the
cycle of $n_k$ edges which includes $e_k$
and $e_1$.
\medskip
\lemma{
The regions $R_1, \dots, R_k$ described
above are distinct. Furthermore, if two regions share more than
one vertex, they share exactly two vertices, $v_0$ and $v_i$, where $v_i$
is adjacent with $v_0$.
}\lemmalabel{\one}
\proof
We first show the regions are distinct.
Suppose that regions $R_i$ and $R_j$,
$1 \le i < j \le k$ are the same, let
this be the region $R$. Then the edges
$e_i, e_{i+1}, e_j, e_{j+1}$ are all
part of the edge set of $R$. Now we
can draw a simple closed curve $C$ in
$R$ which intersects $\Gamma$ only at the vertex
$v_0$, and either $v_{i+1}$ is interior to $C$ while the vertex
$v_i$
is exterior to $C$ or else $v_{i+1}$ is exterior to $C$ while $v_i$ is interior to $C$.
This means that the
removal of the vertex $v_0$ disconnects
$\Gamma$ which contradicts the fact that
$\Gamma$ is 3-connected. Thus the regions
are distinct.
\medskip
We next show that no
pair of the regions $R_1, \dots, R_k$
have more than two vertices in common.
Suppose the regions $R_i$ and
$R_j$, $1 \le i < j \le k$, have a vertex
in common which is neither $v_0$ nor adjacent with $v_0$. (Note that if
$j=i+1 \pmod {k}$ then $R_i$ and $R_j$
will have at least vertices $v_0$ and
$v_{i+1}$ in common.) Let $u$ be a
vertex common to the edge set of $R_i$
and $R_j$ where $u \ne v_i, v_{i+1},
v_j, v_{j+1}$. Let $R = R_i \cup R_j$
Now we can draw a simple closed curve
$C$ in $R$ which intesects $\Gamma$ only at the
vertices $v_0$ and $u$; and either $v_{i+1}$ is interior to $C$ while
the vertex $v_i$ is exterior to $C$ or vice versa.
This means that the removal of the
vertices $v_0$ and $u$ disconnects
$\Gamma$ which contradicts the fact
that $\Gamma$ is 3-connected. Thus
no pair of the regions $R_1, \dots,
R_k$ have more than two vertices in common.
\qed
\medskip
\section{Embeddings}
Let $M$ be a Riemannian 2--manifold. That is, $M$ is a two dimensonal
manifold with a
metric. The Riemannian manifolds considered here
are the Euclidean plane ($\R^2$), the
usual two--dimensional sphere of radius one
($\S^2$), and the hyperbolic plane ($\H^2$).
(See [6] for more information about the hyperbolic plane.)
These three manifolds are used
because for any one of them given a pair of points $x,y$ in the manifold
there is an isometry mapping $x$ to $y$. Furthermore, given any
point, rotation about that point by any angle is an isometry.
An embedding of a graph $\Gamma$
into $M$ is a {\it geometric embedding} if every
edge of $\Gamma$ in $M$ has the same length $\rho$ and
there is a function $\alpha(n)$ such that
every interior angle in every $n$--sided region has measure $\alpha(n)$.
Examples of geometric embeddings of a graph in the Euclidean plane include
tesselations of the plane with squares or hexagons. The Platonic solids
give examples of geometric embeddings of finite graphs in the sphere. A
regular tessalation of the hyperbolic plane with heptagons is an example
of a geometric embedding of a graph in the hyperbolic plane.
A {\it local geometric embedding} of $\Gamma$ at $v_0$
into $M$ is an embedding of a
vertex $v_0$ of $\Gamma$ and all the boundary vertices and edges of all the
regions incident with $v_0$. Furthermore, it is required that all edges
have the same length, $\rho$, and all angles in all $n$--gons have the
same measure, $\alpha(n)$, as in the definition of geometric embedding.
A {\it geometric mapping} of $\Gamma$ into $M$ is a mapping of the vertices
and edges into $M$ which is a local geometric embedding at each vertex
of $\Gamma$.
The
`niceness' of the arrangement of the
regions incident to a vertex $v$ in
$\Gamma$ suggests the possiblity of
embedding $\Gamma$ geometrically in either the Euclidean
plane, the hyperbolic plane, or
the sphere.
The existence
of such embeddings in the Euclidean
and hyperbolic planes are then used
to show that $\Gamma$ has either
quadratic or exponential growth. We
give explicit conditions for when
such embeddings exist.
Let $v_0$ be a fixed vertex of $\Gamma$ and $R_1,R_2,\dots,R_k$ and
$n_1,n_2,\dots,n_k$ be as in Lemma~\one. Consider the sum
$$S=\sum^k_{i=1}(1-{2\over{n_i}}).$$
\medskip
\lemma{The graph $\Gamma$ has a local geometric embedding in either $\R^2$,
$\H^2$ or $\S^2$ depending on whether $S$ is two, greater than
two, or less than two respectively.}\lemmalabel{\local}
\proof
Note that each angle of a regular $n$--gon in the Euclidean plane
has measure $\pi\(1-{2\over n}\)$.
Consequently, $S\pi$ is the sum of what the angles around $v_0$ would be if
each region were regular and the graph were embedded in the Euclidean
plane. Clearly if $S=2$, then there is a local embedding in the Euclidean
plane. We consider the remaining two cases:
\noindent
{\bf Case A:} $S<2$. In this case we find a local embedding in the sphere $S^2$.
Each of the regions $R_1,\dots ,R_k$
can be mapped to a regular $n_i$-gon
in $\S^2$ with sides of length
$\rho$ such that each of these $n_i$-gons
is incident to the image point of $v_0$.
We identify each $R_i$ with its image $n$-gon.
Let each $n_i$-gon, $1 \le i \le k$,
have interior angle $\theta_{n_i, \rho}$.
It is sufficient to show there is a value of
$\rho$ such that $\sum^k_i \theta_{n_{i},
\rho}=2\pi$.
\smallskip
Let $n=\max\{n_i\}$, $1 \le i \le k$, then
we consider values of $\rho$ with $0 \le \rho \le {2\pi\over{n}}$.
Note that the upper bound on $\rho$ comes from the extreme case where
the boundary of a region is a great circle, and each angle is $\pi$.
If $\rho$ is close to zero then an $n$-gon
on the surface of a sphere is close to being
`flat' (as on the Euclidean plane)
so $\lim_{\rho \rightarrow 0}\sum^k_{i=1}
\theta_{n_i, \rho} =
\sum^k_{i=1}(\pi-{2\pi\over{n_i}})
< 2\pi$ by the assumption that
$\sum^k_{i=1}(1-{2\over{n_i}}) < 2$.
\smallskip
We now show that
$\sum^k_{i=1} \theta_{n_{i}, {2\pi\over n}}>2\pi$. Since the angles vary
continuously with $\rho$, this is sufficient to show there is some
$\rho<{2\pi\over n}$ where $\sum^k_{i=1} \theta_{n_{i}, \rho}>2\pi$.
First we consider a few special cases.
\smallskip
\noindent {\bf Subcase 1:} (There is more than
one region among $R_1,\dots, R_k$ with $n$ sides.)
\smallskip
Suppose $R_i$ and $R_j$ are two distinct
polygons with $n$ sides.
Then $n=n_i=n_j$ and $\theta_{n_i,
{2\pi\over{n}}}=
\theta_{n_j, {2\pi\over{n}}}=\pi$, so
since $k \ge 3$ it follows that
$\sum_{i=1}^k\theta_{n_i, {2\pi\over{n}}}
> 2\pi$.
\smallskip
\noindent {\bf Subcase 2:} ($k=3$ and there is a
unique region incident with $v_0$ with $n$ sides.)
We break this subcase into three sub--subcases, based on the
regions incident with $v_0$.
\noindent {\bf (i)} ($k=3$, an n-gon and two 3-gons where $n>3$.)
Suppose that $R_1$
is an $n$-gon and $R_2$ and $R_3$
are both $3$-gons. Now using the fact
that each vertex in $\Gamma$ must have
degree 3 it follows that there is a vertex
of $R_1$ which must have two further
regions incident to it but cannot be
adjacent with a vertex of $R_2$ or
$R_3$. Since such a configuration
is not possible in $\Gamma$ the
above situation cannot occur.
\smallskip
\noindent {\bf (ii)} ($k=3$, one 3-gon and
an n-gon and an m-gon where $n>m>3$.)
Suppose that
$R_1$ is an $n$-gon,
$R_2$ is an $m$-gon and
$R_3$ is a $3$-gon where $n>m>3$.
Let $u \ne v_0$ be the common vertex between
$R_2$ and $R_3$ and $w \ne v_0$ be the
common vertex between $R_3$ and $R_1$.
Now $u$ must also have an $n$-sided
region (with edge $\{w,u\}$) incident
to it and $w$ must also have an $m$-sided
region (with edge $\{w,u\}$) incident to
it. This is not possible.
\smallskip
Observe that parts (i) and (ii)
show that $\Gamma$ cannot have a
3-sided region if $k=3$.
\smallskip
\noindent {\bf (iii)} ($k=3$ and there
is no 3-sided region.)
\smallskip
Suppose that $R_1$
is an $n$-gon, $R_2$ is an $m$-gon
and $R_3$ is a $t$-gon where $n>m \ge t\ge 4$.
Now $\theta_{n_3, {2\pi \over{n}}} >
{\pi \over 2}$ (since $\pi\over 2$ is
the angle in the Euclidean case if $t=4$),
$\theta_{n_2, {2\pi \over{n}}} >
{\pi \over 2}$ , and
$\theta_{n_1, {2\pi \over{n}}} = \pi $, therefore
$\sum_{i=1}^k\theta_{n_i,
{2\pi\over{n}}} > 2\pi$.
\smallskip
Observe that
we now need only consider $k \ge 4$.
\smallskip
\noindent {\bf Subcase 3:} ($k \geq 4$)
Let $R_1$, $R_2$, $R_3$ and $R_4$ be
consecutive
regions incident to the vertex $v_0$.
Suppose that $R_1$ is an $n_1$-gon with $n=n_1$
and
$R_2$, $R_3$ and $R_4$ have
respectively $n_2, n_3$ and $n_4$ sides
where equality may occur. Now
$\theta_{n_1, {2\pi \over{n}}} = \pi$
and $\theta_{n_i,
{2\pi \over{n}}} > {\pi \over 3}$
for $i=2,3,4$ (since at worst
these polygons could be triangles ),
therefore
$\sum_{i=1}^k\theta_{n_i, {2\pi\over{n}}} > 2\pi.$
\smallskip
Subcases 1 through 3 show that for those
configurations of regions which
can occur in $\Gamma$ we always
have $\sum_{i=1}^k\theta_{n_i,
{2\pi\over{n}}} > 2\pi$ where
$n=\max\{n_1, \dots, n_k\}$.
Since $\sum_{i=1}^k\theta_{n_i,
\rho}$ is a continuous function of
$\rho $ there is
a value of $\rho$ such that
$\sum_{i=1}^k\theta_{n_i, \rho} =2\pi$.
\smallskip
\noindent
{\bf Case B:} $S>2$. In this case we find a local embedding in the
hyperbolic plane $\H^2$. The idea is the same as in Case A, except that
we note that as the side length of a regular $n$--gon approaches
infinity, the angles in the $n$--gon approach 0. So, defining
$\theta_{n_i,\rho}$ as an angle in a regular $n$--gon in $\H^2$ with sides
of length $\rho$, we have
$$\lim_{\rho \rightarrow \infty}\sum_{i=1}^k\theta_{n_i, \rho} =0$$
\noindent and
$$\lim_{\rho \rightarrow 0}\sum_{i=1}^k\theta_{n_i, \rho} >2\pi.$$
\noindent
The first limit holds since as the length of $\rho$ increases the
angle of the $n$-gon gets smaller and the second one corresponds
to the Euclidean case. Therefore, there is a
$\rho$ such that $\sum_{i=1}^k\theta_{n_i, \rho}=2\pi$, which says that
$\Gamma$ locally embeds geometrically in $\H^2$.
\qed
\figure{2.25true in}{map.eps}{\map}
Let $g:\Gamma\to M$ be a local geometric embedding where $M$ is either
$\S^2$, $\R^2$, or $\H^2$. With this
embedding, we let $\alpha(n)$ denote the measure of each angle in
an $n$--sided region incident with $v_0$.
We define a mapping $f$ from the walks starting at $v_0$
in $\Gamma$ to walks in $M$ starting at $g(v_0)$.
Let $P=(v_0,v_1,v_2,\dots,v_k)$ be a walk in $\Gamma$ starting
at $v_0$.
Let $x_0=g(v_0)\in M$, and follow a geodesic from $x_0$ to
$x_1=g(v_1)$. Then rotate in $\Gamma$ from the edge $\{v_0,v_1\}$ to the edge
$\{v_1,v_2\}$ counter clockwise and let $n_1,n_2,\dots,n_h$ represent
the number of sides in the regions we rotate through. In $M$ rotate
from the geodesic between $x_0$ and $x_1$ through an angle of
$\sum_{i=1}^h \alpha(n_i)$. Then follow a geodesic from $x_1$
in this direction a distance of $\rho$. Continue this process from
vertex to vertex along $P$ until we reach the end vertex $v_k$.
We define $f(P)$ to be the walk consisting of the union of the
geodesic segments
followed in this process. (See Figure~\map.)
Our next goal is to show that the end point of
$f(P)$ only depends on the end vertex of
$P$. Consequently, we can think of $f$ mapping the graph $\Gamma$ into
$M$. That is, we map a vertex $v$ to the end vertex of
$f(P)$ where $P$ is any walk in
$\Gamma$ starting at $v_0$ and ending at $v$. An edge $\{v,w\}$ is mapped to
the geodesic between $f(v)$ and $f(w)$. (In the sphere, we take the
shortest geodesic between $f(v)$ and $f(w)$.)
We say a walk $P$ starting at $v_0$ is {\it bad} if there is another
walk
starting at $v_0$, say $P'$, such that $P$ and $P'$ have the same end
vertex $v$, but $f(P)$ and $f(P')$ have different end points.
Otherwise, the walk is said to be {\it good}.
\lemma{A walk
$P=(v_0,v_1,\dots, v_i,w,v_i,v_{i+1},\dots ,v_k)$ is good if and only if
the walk
$P'=(v_0,v_1,v_2,\dots,v_{i-1},v_i,v_{i+1},\dots,v_k)$ is
good.}\lemmalabel{\trim}
\proof
This is easy to verify. The point is that the sum
of the values for $a(n)$ around the vertex $v_i$ is $2\pi$.
\qed
Suppose that $P=(v_0,v_1,\dots,v_{k-1},v_k=v_0)$ is a closed walk.
We say that
$P$ {\it ends well} if the last geodesic segment of $f(P)$ is the
geodesic between $g(v_{k-1})$ and $g(v_0)$. In particular, if $P$
ends well, then $P$ is good.
\lemma{If $w_0,\dots ,w_t$ is a cycle
bounding a region in $\Gamma$ then
$P=(v_0,v_1,\dots,v_k=w_0,w_1,w_2,\dots,w_t=v_k,v_{k-1},v_{k-2},\dots,
v_0)$ ends well.
Furthermore, the part of the path $f(P)$ corresponding to
$v_k, v_{k-1},\dots, v_0$ retraces the part corresponding to
$v_0,v_1,\dots,v_k$.}\lemmalabel{\region}
\proof
The cycle part of the walk $P$ maps to a regular $t$-cycle in $M$ by
construction. Consequently, the next edge after the cycle maps to
the same edge as the last edge before the cycle.
\qed
The above idea of a path retracing itself is used during the proof of
the next few lemmas. We first attempt to clarify the concepts involved.
Let $P= (v_0, v_1,\dots, v_{k-1}, v_k=v_0)$ be a closed walk and $Q$ be a
walk which begins at $v_0$. We use $PQ$ to denote the walk which starts at
$v_0$ and first follows $P$ and then follows $Q$.
The path $f(Q)$ is defined to
start with a certain geodesic segment based on the first edge of $Q$.
On the other hand, when completing the closed walk $P$, we need to know that
the next geodesic followed in $f(PQ)$ (corresponding to the first edge
of $Q$) will be the same geodesic as the first one in $f(Q)$. This holds
provided that $P$ ends well.
\lemma{Every cycle $P$ ends well.}\lemmalabel{\cycles}
\proof
We use induction on the number of regions enclosed by
$P=(v_0,v_1,\dots, v_{k-1},v_k=v_0)$
to show that $P$ ends well. If $P$ encloses only one region then
$P$ ends well by Lemma~\region.
\figure{3true in}{regions.eps}{\regions}
Suppose that $P=(v_0,v_1,v_2,\dots, v_k=v_0)$
encloses more than one region. Then by
trimming one region as in Figure~\regions, we can break the area
enclosed by $P$ into one region and the union of the rest of the
regions. That is, we have two cycles,
$$P'=(v_0,v_1,\dots,v_t,w_1,w_2,\dots, w_r,v_s,v_{s+1},\dots,v_k=v_0)$$
and
$$P''=(v_t,w_1,w_2,\dots, w_r,v_s,v_{s-1},\dots, v_t)$$
where $P'$ encloses fewer regions than
$P$ encloses and $P''$ encloses one region. By induction, $P'$ ends
well.
Furthermore, by Lemma~\region\ the closed walk
$$Q=(v_0,v_1,\dots,v_t,\dots, v_s,w_r,w_{r-1},\dots,w_1,v_t,v_{t-1},v_{t-2},\dots, v_0)$$
ends well. But then, the walk $QP'$ ends well since the path $f(Q)$ returns
on the same geodesic segment as it begins. We deduce the cycle $P$ is
good
by repeatedly applying Lemma~\trim\ to $QP$.
Furthermore, it
is clear that the last geodesic segment of $f(P)$ is the same as the
last geodesic segment of $f(P')$ in the case where $P''$ does not include
$v_k=v_0$ and it is the same as the last geodesic segment of $f(P'')$
otherwise. In either case, $P$ ends well.
\qed
If $P=(v_0,v_1,\dots,v_k)$ is a walk, we denote the walk
$(v_k,v_{k-1},\dots,v_0)$ by $P^{-1}$.
\lemma{Let $C=(v_0=u_0,u_1,\dots, u_k=v_0)$ be a closed walk
which ends well. Let $\phi$ be an
automorphism of $\Gamma$ with $\phi(v_0)=w_0$. Let
$P=(v_0,v_1,\dots, v_r=w_0)$ be a walk from $v_0$ to $w_0$. Then the walk
$P\phi(C)P^{-1}=(v_0,v_1,\dots,v_r=\phi(u_0),\phi(u_1),\dots,\phi(u_k)
=v_r,v_{r-1},\dots,v_1,v_0)$ ends well.}\lemmalabel{\lollypop}
\proof
The fact that $C$ ends well implies that it would end well even if
instead of starting at the point $g(v_0)$ we start at an arbitary point
in $M$. Since in the construction of $f(P\phi(C)P^{-1})$, the part
$\phi(C)$ is traced in the same way as $C$ when computing $f(C)$ except
that we start at a different point, it follows that the image of
$P^{-1}$ traces the path of the image of $P$ backward.
\qed
\lemma{Every closed walk $P$ ends well.}\lemmalabel{\closedwalks}
\proof
Suppose not. Let $P=(v_0,v_1,\dots, v_k=v_0)$
be a closed walk of minimal length which does not
end well. The closed walk $P$ is not a cycle by Lemma~\cycles. Let $i$
be the smallest positive integer such that there is a $j$ with
$v_i=v_j$. Let $\phi$ be an automorphism of $\Gamma$ with
$\phi(v_0)=v_i$. The closed walk $C=\phi^{-1}(v_i,v_{i+1},\dots,v_j)$ has
length strictly smaller than the length of
$P$. Therefore $C$ ends well. By
Lemma~\lollypop, the walk $W=(v_0,v_1,\dots, v_j=v_i
,v_{i-1},v_{i-2},\dots,v_0)$ ends well. Furthermore, the closed walk
$C'=(v_0,v_1,\dots,v_i=v_j,v_{j+1},v_{j+2},\dots, v_k=v_0)$ ends well
as its length is less than $k$.
Therefore, the closed walk $WC'$ ends well. Now by applying
Lemma~\trim, it follows that $P$ ends well.
\qed
\lemma{Let $g$ be a local geometric embedding of $\Gamma$ at $v_0$ into
either $\R^2$, $\S^2$, or $\H^2$. Let $P$ and $P'$ be two paths in
$\Gamma$ each of which begins at the vertex $v_0$ and finishes at the
vertex $v$.
Then
$f(P)$ and $f(P')$ have the same end point.}\lemmalabel{\extend}
\proof
Suppose that $P$ and $P'$ are both $v_0v$--walks. Then the walk
$C=P'P^{-1}$ is a closed walk. By Lemma~\closedwalks, $C$ ends well.
Since $C$ is a closed walk, following $f(C)$ backward is the
same as following $f(P)$ forward up until the end of $P$. But this is
the end point of $f(P')$. Therefore, $f(P)$ and $f(P')$ have the same
end point.
\qed
\theorem{There is a geometric mapping of $\Gamma$ into either $\R^2$,
$\H^2$ or $\S^2$ depending on whether
$S=\sum^k_{i=1}(1-{2\over{n_i}})$ is two,
greater than two, or
less than two respectively.}\theoremlabel{\geo}
\proof
By Lemma~\local, $\Gamma$ has a local geometric embedding into the
indicated manifold. By construction, the mapping of Lemma~\extend\ is
a local geometric mapping at each vertex.
\qed
\lemma{Let $f$ be a geometric mapping from $\Gamma$ to $M$. Then $f$
extends to a covering projection
map from $\R^2$ onto $M$.}\lemmalabel{\covering}
\proof
We first extend $f$ by noting that Whitney's Theorem implies that if
$C$ is a cycle bounding a region of $\Gamma$, then $f(C)$ is a cycle
bounding a region of $f(\Gamma)$. Since the regions bounded by $C$
and $f(C)$ are homeomorphic, we extend $f$ to all the regions
of $\Gamma$ by mapping each region by a homeomorphism to the
corresponding region of $f(\Gamma)$. It is clear that $f$ is
continuous.
Let $x\in \R^2$. Either $x$ is a vertex of $\Gamma$, $x$ is interior to
an edge of
$\Gamma$, or else $x$ is interior to a region of $\Gamma$.
Since the mapping $f$ is geometric, each region maps to a region
consisting of a regular $n$--gon with side length $\rho$. For each of
the three possibilities for $x$, there is an $\epsilon>0$ and a
neighborhood of $x$ such that the neighborhood of $x$ maps onto an
$\epsilon$ neighborhood of $f(x)$. This implies that $f$ is an open
mapping, but even more, it implies that for some $\epsilon$,
if $y\in M$ is
in the image of $f$ then every point within $\epsilon$ of $y$ is also
in the image of $f$.
Suppose that $f$ is not onto. Then there is a $y\in M$ such that
$f(x)\not=y$ for every $x\in \R^2$. Let $x_0$ be any point such that
${\rm dist}(f(x_0),y)<\inf\{{\rm dist}(f(x),y)|x\in \R^2\}
+{\epsilon\over 2}$. Then
every point within $\epsilon$ of $f(x_0)$ is in the image of $f$, which
is a contradiction. Therefore, $f$ is onto.
\figure{2.25true in}{delta.eps}{\deltafig}
Given a vertex $v\in V(\Gamma)$ let
$N(v)$ be the union of the closed regions
incident with $v$.
The shaded region in Figure~\deltafig\ represents
$N(u_0)$. Since $f$ is a local geometric mapping, at each
vertex $v$, $f|_{N(v)}$ is a homeomorphism onto $f(N(v))$. Given a point
$x$ in $\R^2$, let $w\in V(\Gamma)$ be a vertex such that $x$ is in the
interior of $N(w)$.
Now, for each vertex $u$ in $N(w)$, let $d_u$ be the distance in $M$
between $f(u)$ and $f(x)$. Let $u_0$ be a vertex in $N(w)$
where this distance is minimized. Notice that there is a $\delta$
(independent of $x$) with the property that every point in $M$ within
$\delta$ of $f(x)$ is in $f(N(u_0))$. See Figure~\deltafig.
We now show the even covering property. Let $y\in M$ and let $U$ be
the disk centered at $y$ with radius $\delta\over 2$. We show that
$f^{-1}(U) = \cup U_i$ such that $U_i\cap U_j=\emptyset$ for $i\not= j$
and $f|_{U_i}:U_i\to U$ is a homeomorphism. Let
$x\in f^{-1}(U)$ and $u_0$ be the vertex in $N(y)$ such that the
distance between $f(u_0)$ and $f(x)$ in $M$ is a minimum. Now it follows that
$f|_{f^{-1}(U)\cap N(u_0)}:f^{-1}(U)\cap N(u_0)\to U$ is a homeomorphism
as $f$ is a geometric mapping. Therefore, $f$ covers $U$ evenly. So
$f$ is a covering projection map.
\qed
\theorem{There is a geometric embedding of $\Gamma$ into either $\R^2$
or $\H^2$. Let $S=\sum^k_{i=1}(1-{2\over{n_i}})$, then
$S\geq 2$. When $S=2$
the embedding is into $\R^2$, whereas for $S>2$ the
embedding is into $\H^2$.}\theoremlabel{\embedding}
\proof
Recall that for any covering $f:X\to Y$, if $Y$ is simply connected then
$f$ is a homeomorphism. Since $\R^2$ and $\S^2$ are not homeomorphic,
there is no covering from $\R^2$ to $\S^2$. Consequently, by
Lemma~\covering\ and Theorem~\geo\ it follows that
$S\geq 2$. Also, by Lemma~\covering\ and Theorem~\geo\
there is a homeomorphism from $\R^2$ onto either $\R^2$ or $\H^2$ which,
when restricted to $\Gamma$, gives a geometric embedding.
\qed
\section{Growth Rate}
\medskip
The {\it growth function} of a graph
$\Gamma$ with respect to any vertex $v$ in
$\Gamma$, is defined by
$$G_{\Gamma}( n)=|\{u \in V(\Gamma)|d(v,u)
\le n \}|,\,\,\,\ {\rm for\,\, all\,\, n} \in N.$$
Of course, if $\Gamma$ is vertex transitive then the growth rate is
independent of the choice of $v$.
We say that $\Gamma$ has {\it exponential growth}
if there exist constants $c_1>c_2 > 1$ such that
$c_1^n\ge G_{\Gamma}( n) \ge c_2^n$ holds for all sufficiently large $n \in N$.
Otherwise $\Gamma$ has nonexponential growth.
In particular, $\Gamma$ has {\it quadratic growth}
if $c_1n^2 \le G_{\Gamma}( n) \le c_2n^2$ holds for some positive
constants $c_1$ and $c_2$.
\medskip
We use the fact that any planar, locally finite, vertex
transitive, 1-ended graph $\Gamma$ can be geometrically
embedded in either
the Euclidean or hyperbolic plane to determine the growth
rate of $\Gamma$. In each case we use the geometry of
the plane in which $\Gamma$ is embedded.
In both cases we estimate
the number of vertices within a circle of fixed radius and the
result is what we would intuitively expect. In the Euclidean
case the area of this circle is of course $\pi r^2$,
where $r$ is the radius,
and we get quadratic growth. For the hyperbolic case the area
is $2 \pi (\cosh r -1)$, where $r$ is the hyperbolic radius,
and we get exponential growth.
\medskip
\theorem{Let $\Gamma$ be a planar,
locally finite, vertex transitive,
1--ended graph with valence $k$.
If $S=\sum^k_{i=1}(1-{2\over{n_i}}) = 2$
then $\Gamma$ has quadratic growth
and if $S=\sum^k_{i=1}(1-{2\over{n_i}}) > 2$
then $\Gamma$ has exponential growth.
}\theoremlabel{\four}
\proof
Let $v_0$ be a vertex in $\Gamma$. In both the following cases we
determine the radii (as linear functions of $n$)
of two discs centered at $v_0$ such that all vertices within the smaller
disk are within $n$ steps of $v_0$ and all vertices within $n$ steps of
$v_0$ lie within the larger disk. The number of vertices within these
respective discs give lower and upper bounds for the growth rate of
$\Gamma$.
{\bf Case A:} $S=2$.
In this case, we may assume by Theorem~\embedding\
that $\Gamma$ is embedded geometrically in the Euclidean
plane.
Let $C(n)$ be the number of vertices within (graph) distance $n$ of
a fixed vertex $v_0$ in $\Gamma$. To determine an upper
bound on $C(n)$ we count the number
of vertices in $\Gamma$ within a disc of radius approximately $n\rho$
centered at
$v_0$ in the Euclidean plane.
Let $\Gamma^*$ be the dual graph
of $\Gamma$ in the Euclidean plane. In this dual graph
each polygonal face represents a vertex of $\Gamma$.
By vertex transitivity of $\Gamma$, all regions of $\Gamma^*$ are
congruent. Let $\beta$ be the diameter of one of these regions.
Consider a circle of radius $r=n\rho+\beta$ in $\R^2$ centered at $v_0$.
Let $a$ be the
area of each region in $\Gamma^*$,
then
$${\pi r^2 \over a} \geq C(n).$$
\noindent
This follows as
a region of $\Gamma^*$ corresponding to a vertex in $\Gamma$ within
$n$ (graph distance) of $v_0$ is completely contained in the disk
centered at $v_0$ and radius $r$.
Therefore, $C(n)\leq c_1n^2$ for some constant $c_1$.
\medskip
Now we obtain a lower bound on $C(n)$.
Let $x_0$ be a vertex of $\Gamma$ with distance (in $\R^2$) $r$ from
$v_0$. Let $L$ be a
geodesic from $x_0$ to $v_0$. Let $x$ be any point in $\R^2$ and $x'$ be
the closest vertex to $x$, then, as pointed out in Lemma 2.8, the disk
centered at $x$ with radius $\delta$ is contained in $N(x')$. Begin
traversing $L$ at $x_0$, since this is already a vertex a segment having
length at least $\delta$ is contained in $N(x_0')$. Let $x_1$ be the
point where $L$ exits $N(x_0')$ and $x_1'$ be the closest vertex to $x_1$.
Again, starting at $x_1$ and following $L$
toward $v_0$, one would move along $L$ at least a distance $\delta$
before exiting $N(x_1')$. Continuing this process, it is clear that one
would have to pass through at most $r\over \delta$ sets of the form
$N(x_i')$. Now, to get from any point in $N(x')$ to any other point in
$N(x')$ takes at most $b$ steps for some fixed $b$ independent of $x$.
Therefore, there is a path in $\Gamma$ from $x_0$ to $v_0$ of (graph)
length at most ${r\over\delta}b$. Therefore, every vertex in a circle of
radius $n\delta\over b$ centered at $v_0$ is within $n$ steps of $v_0$
in $\Gamma$. This gives a quadratic lower bound on $C(n)$. Therefore,
$\Gamma$ has quadratic growth.
\bigskip
\noindent
{\bf Case B:} $S>2$.
Here we can assume that $\Gamma$ is geometrically embedded in the
hyperbolic plane. The argument is the same as in the
Euclidean case with just one essential difference. The area of
a disk centered at $v_0$ in $\H^2$ grows exponentially as a function of
$r$. Consequently, exponential upper and lower bounds follow
just as quadratic
bounds follow in the Euclidean case.
\bigskip
\centerline{References}
\medskip
\bibitem{1}{C. Bonnington, W. Imrich and M.Watkins,
Separating double rays
in locally finite planar graphs,
Discrete Mathematics {\bf 145}
(1995) 61--72.}
\bibitem{2} {R. Halin, Automorphisms and
endomorphisms of infinite, locally
finite graphs,
Abh. Math. Sem. Univ. Hamburg
{\bf 39}(1973) 251-283.}
\bibitem{3}{W. Imrich, On Whitney's theorem
on the unique imbeddability of
3-connected planar graphs,
in: M. Fiedler, ed., Recent Advances
in Graph Theory (Academia
Praha, Prague, 1975) 303--306.}
\bibitem{4}{C. Thomasen, Duality of
infinite graphs,
Combinatorica {\bf 1}(1982)
285--288.}
\bibitem{5}{H. Whitney, Non-separable and
planar graphs,
Trans. Amer. Math. Soc.
{\bf 34}(1932) 339--362.}
\bibitem{6}{H. Zeischang, Finite Groups of Mapping Classes of Surfaces,
Lecture Notes in Mathematics No. 875, Springer--Verlag, New York, 1981}
\bye