On the Number of Simple Cycles in Planar Graphs
Helmut Alt, U. Fuchs, Klaus Kriegel · Combinatorics Probability Computing · 1999
Let C(G) denote the number of simple cycles of a graph G and let C(n) be the maximum of C(G) over all planar graphs with n nodes. We present a lower bound on C(n), constructing graphs with at least 2.28n cycles. Applying some probabilistic arguments we prove an upper bound of 3.37n. We also discuss this question restricted to the subclasses of grid graphs, bipartite graphs, and 3-colourable triangulated graphs.