{"id":{"repo_id":"wku-diss","oai_identifier":"oai:digitalcommons.wku.edu:theses-1443"},"canonical_url":"https://search.dev.ndltd.org/etd/wku-diss/oai:digitalcommons.wku.edu:theses-1443","repository":{"repo_id":"wku-diss","name":"Western Kentucky University","base_url":"https://digitalcommons.wku.edu/do/oai/"},"display":{"title":"An Algorithm to Generate 4-Regular Planar Hamiltonian Graphs","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Ascigil, Mehmet"],"institution":null,"degree_name":"Master of Computer Science","degree_level":null,"degree_discipline":"Department of Mathematics and Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2006,"date_issued":"2006-08-01T07:00:00Z","date_published":"2006-08-01T07:00:00Z","updated_at":"2026-07-24T06:07:28Z","subjects":["Computer Sciences"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.wku.edu/theses/440","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Ascigil, Mehmet"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Department of Mathematics and Computer Science"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Computer Science"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Sciences"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.wku.edu/theses/440"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["An Algorithm to Generate 4-Regular Planar Hamiltonian Graphs"]}]}],"canonical_facts":{"dc:creator":["Ascigil, Mehmet"],"dc:description.abstract":["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."],"dc:identifier":["https://digitalcommons.wku.edu/theses/440"],"dc:subject":["Computer Sciences"],"dc:title":["An Algorithm to Generate 4-Regular Planar Hamiltonian Graphs"],"dc:type":["Thesis"],"thesis:degree_discipline":["Department of Mathematics and Computer Science"],"thesis:degree_name":["Master of Computer Science"]},"updated_at":"2026-07-24T06:07:28Z"}