I am considering an undirected planar graph $\mathcal{G} = (E, V)$ with no loop. If necessary, we can assume that there are no node of degree one. It is however not excluded that there are multiple vertices between two nodes. I now choose a node $v$. I would like to find the number of simple paths that go from $v$ to $v$, i.e., the number of walks starting and ending at $v$ that don't go through any vertex more than once.
For the purpose of the illustration, Consider:
This graph has $6$ different paths connecting $v = 1$ to itself.
I found a non-polynomial time algorithm to count these paths, but I would like to find a formula for this.
Given a vertex $v$ of a graph $\mathcal G$ a walk starting and ending at $v$ that don't going through any vertex of $\mathcal G$ more than once we’ll call a $v$-cycle.
If $\mathcal G$ is $n$-gon in which there are $a_i$ instances of $i$-th edge of $n$-gon, then for each vertex $v$ of $\mathcal G$ there is exactly $\prod a_i$ $v$-cycles of non-zero length. In particular, when all $a_i=2$ then the number of $v$-cycles if $2^{|E|/2}$. If we wish to have a graph without multiple edges with exponential lower bound for the number of $v$-cycles, then we can subdivide each second instance of a multiple edge by a vertex.
The remaining part of my answer is conjectural, and I’m going to think about it more later.
Nevertheless, I guess that that for each vertex $v$ of a planar graph $\mathcal G$ without multiple edges there is at most exponentially many $v$-cycles in $\mathcal G$. This claim also may imply that for each vertex $v$ of a planar graph $\mathcal G$ there is at most exponentially of $|E|$ many $v$-paths in $\mathcal G$.
In order to prove this conjecture, for the simplicity if necessary, we can assume that there are no node of degree one, because such a node cannot belong to any cycle. Next we associate the graph $\mathcal G$ with its arbitrary plane drawing. Then I guess that each cycle of $\mathcal G$ is uniquely determined by a set of faces which it bounds. Since $\mathcal G$ has $O(|E|)$ faces, there are at most $2^{O(|E|)}$ cycles in $\mathcal G$.
Also are interesting grid graphs. Let $v$ be the origin of an infinite square grid graph $\mathcal G$. I guess that the sets of faces of $\mathcal G$ bounded by $v$-cycles are exactly sets $S^*$ of vertices of the dual graph $\mathcal G^*=(V^*,E^*)$ such $v$ has and incident face both in $S^*$ and $V^*\setminus S^*$ and both subgraph induced on $S^*$ and $V^*\setminus S^*$ are connected. Since the dual $G^*$ is again an infinite square grid graph, it turns out that we went close to a recent percolation related counting problem. Namely, we have to count a number of sets $S^*$ of the graph $\mathcal G$ such that induced by $S^*$ subgraph of $\mathcal G$ is connected (that is fixed a polyominoes) without holes and $S^*$ contains at least one and at most three faces of four faces of $\mathcal G$ incident to $v$. I expect that there exists exponentially many such sets $S^*$. Then for grid graphs we should have exponentially many $v$-cycles of a given length. I expect that there are still exponentially many $v$-cycles even when $\mathcal G$ is a rectangular grid and the $v$-cycle should contain all vertices of $\mathcal G$. The number of $v$-cycles is the number of Hamiltonian cycles, which are known as rook cycles, see also this related question. I guess that for sufficiently wide grids there are exponentially many rook cycles.