An infinite $r$-regular graph is a graph with $\infty$ vertices where each vertex touches precisely $r$ edges.
We say an $r$-regular graph can be embedded in the $R^2$ Euclidean plane if its set of edges and vertices can be represented as a set of points on the plane where each point is connected via an edge to precisely the $r$ closest points to it. For example, some $4$-regular graphs can be embedded in the plane by placing each vertex of the graph on a unique point $(m,n)$ on the plane where $m$ and $n$ are integers. Some $8$-regular graphs can be embedded using the same placement.
The question is: for what values of $r$ do there exist connected $r$-regular graphs that can be embedded in the plane?
The graphs need not be planar, but an answer dealing with the planar case is welcome.
For every $r$ there exists a planar, connected $r$-regular graph, and here is an explicit construction:
Start with a vertex at $(1,0)$. Connect it to vertices $(i,1)$ for $i=1,2,...,r$. Now, draw vertices at $(i,2)$ for $i=1,...,r(r-1)$. Connect $(1,1)$ with $(1,2),...,(r-1,2)$. Connect $(2,1)$ with $(r,1),...,(2(r-1),1)$, etc.
Now draw vertices at $(i,3)$ for $i=1,...,r(r-1)^2$, and connect every vertex $(i,2)$ with $r-1$ of these. Continue like that.
It's easy to see that this construction will result with a connected, planar, $r$-regular tree.
Here is beginning of the construction for $r=3$: