Hamiltonian cycle on graphs without small cycles
This unpublished manuscript by Hougardy, Emden-Weinert and Kreuter in 1997 
provided a simple proof for the following result which is much stronger than the result pointed out in 
Kristoffer Arnsfelt Hansen's answer:


  For any given rational number $0\le r &lt;1/2$, the Hamiltonian cycle probem remains NP-complete even if restricted to bipartite planar $n$-vertex graphs of maximum degree 3 and girth $\ge n^r$.


The manuscript contains also similar results for other problems such as Dominating set, Max cut, VFS, etc.