Counting cycles in planar triangulations

We investigate the minimum number of cycles of specified lengths in planar n-vertex triangulations G. We prove that this number is Ω(n) for any cycle length at most [Formula presented], where rad(G^⁎) denotes the radius of the triangulation's dual, which is at least logarithmic but can be linear in the order of the triangulation. We also show that there exist planar hamiltonian n-vertex triangulations containing O(n) many k-cycles for any k∈{⌈n−n5⌉,…,n}. Furthermore, we prove that planar 4-connected n-vertex triangulations contain Ω(n) many k-cycles for every k∈{3,…,n}, and that, under certain additional conditions, they contain Ω(n²) k-cycles for many values of k, including n.