Complexity of counting m-cycles in a graph with n nodes
Perhaps this paper which deals with cycle lengths in planar graphs might be of value:

Li, Ming-Chu; Corneil, Derek G.; Mendelsohn, Eric (2000), "Pancyclicity and NP-completeness in planar graphs", Discrete Applied Mathematics 98 (3): 219–225.