Xrfgtjtk

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.

I found a non-polynomial time algorithm to count these paths,

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.