An Algorithm to Generate 4-Regular Planar Hamiltonian Graphs

In this paper, the problem of randomly generating 4-regular planar Hamiltonian graphs is discussed and a solution is described. An algorithm which efficiently generates the graphs in linear time and in a near-uniform manner is given. In addition, a formula is provided that determines the total number of such graphs. The generation of graphs starts with forming the Hamiltonian cycle of the final graph. Each vertex is randomly assigned to be connected with zero. one. Or two edges in the area bounded by the Hamiltonian cycle. A positive prefix vector is used to determine all the edges in the area bounded by the Hamiltonian cycle. Another positive prefix vector is used for determining the edges in the area not bounded by the Hamiltonian cycle, forming the final graph