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.

翻译：我们研究在三角三角平面图上计算所有周期或自我消遣行走(SAWs)的问题。 我们为此计时问题提出了一个次要费用计算算法 $2 ⁇ O(\\ sqrt{n}) 。 此算法使用的技术成分包括平面分隔线定理以及使用莫兹金路径和莫兹金数字进行精密分析。 然后我们可以将这一算法调整为在次富裕时间里统一采样的视觉。 我们工作的动机是地理分布图问题 。