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.

Name thesis:degree_name

Master of Computer Science

Discipline thesis:degree_discipline

Department of Mathematics and Computer Science

Year

2006

Author dc:creator

• Ascigil, Mehmet

• Computer Sciences

Repository record dc:identifier

https://digitalcommons.wku.edu/theses/440

OAI identifier oai:identifier

oai:digitalcommons.wku.edu:theses-1443