This paper describes the study of a special class of 4-regular plane graphs that are Hamiltonian. These graphs are of particular interest in knot theory. An algorithm is presented that randomly generates such graphs with \( n \) vertices with a fixed (and oriented) Hamiltonian cycle in \( O(n) \) time. An exact count of the number of such graphs with \( n \) vertices is obtained, and the asymptotic growth rate of this number is determined. Numerical evidence is provided to show that the algorithm can be modified to generate these graphs with a near uniform probability. This can be considered a first step in generating large random knots without bias.