  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 counting problem. Among the technical ingredients used in
this algorithm are the planar separator theorem and a delicate analysis using
pairs of Motzkin paths and Motzkin numbers. We can then adapt this algorithm to
uniformly sample SAWs, in subexponential time. Our work is motivated by the
problem of gerrymandered districting maps.

Data Structures and Algorithms;Combinatorics