# Can the number of cycles in non-planar undirected graphs be computed in reasonable time?

Background: I'm experimenting with programs that create non-planar undirected graphs from three-dimensional meshes. A graph created by program A is not necessarily isomorphic to one created by program B. However the number of cycles should be identical, else something went wrong (a small triangle was missed or seam between two triangles was accidentally filled).

Now I've been looking for a way to compute the number of cycles in these graphs. I found a few simple algorithms which run in non-polynomial time. However I cannot find any references that state that there is no polynomial time solution. Note that I do not care about the actual cycles, I only care about the number of cycles. Would that give me some opportunities to take short-cuts?

If this is totally impossible (which I can image, this could be closely related to the graph-isomorphism problem) are there any other properties of graphs that say something about the layout-of the graph but do not care about an extra node if it only has one incoming and one outgoing edge. To illustrate I would like the following two graphs to be equal in the terms of this property.

My definition of reasonable here is that it can be computed within 15 minute on a modern computer, for a graph with 10.000 edges. I imagine even some non-polynomial solutions that use dynamic programming should be able to achieve this.

-

You probably want to use Johnson's algorithm. This finds all the cycles in a directed graph in $O((n+e)(c+1))$ time, where $n$ is the number of vertices, $e$ is the number of edges, and $c$ is the number of cycles. Of course you can use this algorithm to find cycles in undirected graphs by creating a directed version of your undirected graph $G$ with edges $u\rightarrow v$ and $v \rightarrow u$ for each $(u,v) \in E(G)$, running the algorithm on the directed graph, and removing the duplicate cycles.