On the Number of Simple Cycles in Planar Graphs

Helmut Alt
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin, Germany
email: alt@inf.fu-berlin.de

Ulrich Fuchs
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin, Germany
email: fuchs@inf.fu-berlin.de

Klaus Kriegel
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin, Germany
email: kriegel@inf.fu-berlin.de

Report B 97-08
September 1997

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.28ⁿ cylces. Applying some probabilistic arguments we prove an upper bound of 3.37ⁿ.

We also discuss this question restricted to the subclasses of grid graphs, bipartite graphs, and of 3-colorable triangulated graphs.

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-97-08.ps.gz