Technical Reports

The ICICS/CS Reading Room

UBC CS TR-88-02 Summary

On Lower Bound for Short Noncontractible Cycles in Embedded Graphs, January 1988 Teresa Maria Przytycka and J. H. Przytycki

Let $C_{g,n}$ be a constant such that for each triangulation of a surface of genus $g$ with a graph of $n$ vertices there exists a noncontractible cycle of length at most $C_{g,n}$. Hutchinson in [H87] conjectures that $C(g,n)$ = $O(\sqrt{n/g})$ for $g > 0$. In this paper, we present a construction of a triangulation which disproves this conjecture.

If you have any questions or comments regarding this page please send mail to