Counting Cycles on Planar Graphs in Subexponential Time

Jin-Yi Cai, Ashwin Maran

We study the problem of counting all cycles or self-avoiding walks (SAWs) on triangulated planar graphs. We present a subexponential $2^{O(\sqrt{n})}$ time algorithm for this count…