%\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


