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