# Number of simple paths in undirected planar graph

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.

• But you wrote "with no loop" while your illustration has one. Can you give an illustration of what you actually seek? – David G. Stork Dec 20 '18 at 0:35
• @DavidG.Stork No, it has no loops, because a loop is an edge joining a vertex to itself. I think the question is correct. – Alex Ravsky Dec 20 '18 at 2:20
• Yes, @DavidG.Stork, you are right. I allow the graph to have multiple vertices between two nodes (as in the example I gave) but no loops. – V. Goepp Dec 21 '18 at 16:12

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.