Alt, Helmut; Fuchs, Ulrich; Kriegel, Klaus On the number of simple cycles in planar graphs. (English) Zbl 0886.05082 Möhring, Rolf H. (ed.), Graph-theoretic concepts in computer science. 23rd international workshop, WG ’97, Berlin, Germany, June 18–20, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1335, 15-24 (1997). Summary: 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.27^n\) cycles. Applying some probabilistic arguments we prove an upper bound of \(3.37^n\). We also discuss this question restricted to the subclasses of grid graphs, bipartite graphs, and 3-colorable triangulated graphs.For the entire collection see [Zbl 0877.00011]. Cited in 1 Document MSC: 05C30 Enumeration in graph theory 05C38 Paths and cycles 05C10 Planar graphs; geometric and topological aspects of graph theory 05C15 Coloring of graphs and hypergraphs Keywords:embedding; number of simple cycles; planar graphs; bound; grid graphs; triangulated graphs PDFBibTeX XMLCite \textit{H. Alt} et al., Lect. Notes Comput. Sci. 1335, 15--24 (1997; Zbl 0886.05082)