Finding Short Cycles in an Embedded Graph in Polynomial Time

Han Ren, Ni Cao

Let ${\mathcal{C}}_1$ be the set of fundamental cycles of breadth-first-search trees in a graph $G$ and ${\mathcal{C}}_2$ the set of the sums of two cycles in ${\mathcal{C}}_1$. Then we show t…