A graph whose closure is the complete graph is Hamiltonian by the Bondy-Chvátal theorem, but I haven't found a polynomial algorithm for finding a Hamiltonian cycle in such a graph. Is there one that we know of?
https://en.wikipedia.org/wiki/Bondy%E2%80%93Chv%C3%A1tal_theorem#Bondy.E2.80.93Chv.C3.A1tal_theorem
I don't see that class here http://www.graphclasses.org/classes/problem_Hamiltonian_cycle.html
Tony's method works in the general case. Let $e_1, e_2, \ldots, e_N$ be the edges that are added to $G$, in the order they are added, to make the complete graph. Choose an arbitrary hamiltonian cycle in the complete graph. Now remove $e_N$. If $e_N$ was in the cycle, you can find a new cycle that avoids it by the cross-over technique that Tony explains. Then remove $e_{N-1}$ in the same way. Continue until you removed all the edges that were added. Since each step takes time $O(n)$, the total time is $O(nN)=O(n^3)$. I don't believe this is best possible and wouldn't be surprised if this can be implemented in time $O(n^2)$.
In the case that your graph satisfies the conditions of Ore's theorem (so that it's Ore closure is $K_n$ after 'one step'), there is an easy algorithm to find a Hamilton cycle.
Arbitrarily arrange the vertices $v_1, \dots, v_n$ in a circle. If all consecutive vertices $v_i$ and $v_{i+1}$ are adjacent in $G$ (subscripts are read mod $n$), then we are done. Otherwise, if $v_i$ and $v_{i+1}$ are non-adjacent, find an index $j$ such that $v_i$ is adjacent to $v_j$ and $v_{i+1}$ is adjacent to $v_{j+1}$. Such an index $j$ is guaranteed to exist by Ore's condition, and can be found in time $O(n)$. Change the ordering of the vertices in the obvious way, and note that the number of non-adjacent consecutive vertices has gone down. After at most $n$ steps, we will output a Hamilton cycle, so this takes $O(n^2)$ in total.
