@inproceedings{bfc253074ecc46acb8963967f45187d1,

title = "On the number of cycles in planar graphs",

abstract = "We investigate the maximum number of simple cycles and the maximum number of Hamiltonian cycles in a planar graph G with n vertices. Using the transfer matrix method we construct a family of graphs which have at least 2.4262 n simple cycles and at least 2.0845 n Hamilton cycles. Based on counting arguments for perfect matchings we prove that 2.3404 n is an upper bound for the number of Hamiltonian cycles. Moreover, we obtain upper bounds for the number of simple cycles of a given length with a face coloring technique. Combining both, we show that there is no planar graph with more than 2.8927 n simple cycles. This reduces the previous gap between the upper and lower bound for the exponential growth from 1.03 to 0.46.",

author = "K. Buchin and C. Knauer and K. Kriegel and A. Schulz and R. Seidel",

year = "2007",

doi = "10.1007/978-3-540-73545-8_12",

language = "English",

isbn = "978-3-540-73544-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "97--107",

editor = "G. Lin",

booktitle = "Computing and Combinatorics (13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007. Proceedings)",

address = "Germany",

}