Packing 1-plane Hamiltonian cycles in complete geometric graphs
Counting the number of Hamiltonian cycles that are contained in a geometric graph is #P-complete even if the graph is known to be planar [15]. A relaxation for problems in plane geometric graphs is to allow the geometric graphs to be 1-plane, that is, each of its edges is crossed at most once. We co...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Faculty of Sciences and Mathematics, University of Nis
2019
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/81605/1/PLANE.pdf |
| _version_ | 1796980942224490496 |
|---|---|
| author | Trao, Hazim Michman Ali, Niran Abbas Chia, Gek L. Kilicman, Adem |
| author_facet | Trao, Hazim Michman Ali, Niran Abbas Chia, Gek L. Kilicman, Adem |
| author_sort | Trao, Hazim Michman |
| collection | UPM |
| description | Counting the number of Hamiltonian cycles that are contained in a geometric graph is #P-complete even if the graph is known to be planar [15]. A relaxation for problems in plane geometric graphs is to allow the geometric graphs to be 1-plane, that is, each of its edges is crossed at most once. We consider the following question: For any set P of n points in the plane, how many 1-plane Hamiltonian cycles can be packed into a complete geometric graph Kn? We investigate the problem by taking two different situations of P, namely, when P is in convex position, wheel configurations position. For points in general position we prove the lower bound of k − 1 where n = 2k + h and 0 ≤ h < 2k. In all of the situations, we investigate the constructions of the graphs obtained. |
| first_indexed | 2024-03-06T10:30:28Z |
| format | Article |
| id | upm.eprints-81605 |
| institution | Universiti Putra Malaysia |
| language | English |
| last_indexed | 2024-03-06T10:30:28Z |
| publishDate | 2019 |
| publisher | Faculty of Sciences and Mathematics, University of Nis |
| record_format | dspace |
| spelling | upm.eprints-816052021-06-20T16:25:49Z http://psasir.upm.edu.my/id/eprint/81605/ Packing 1-plane Hamiltonian cycles in complete geometric graphs Trao, Hazim Michman Ali, Niran Abbas Chia, Gek L. Kilicman, Adem Counting the number of Hamiltonian cycles that are contained in a geometric graph is #P-complete even if the graph is known to be planar [15]. A relaxation for problems in plane geometric graphs is to allow the geometric graphs to be 1-plane, that is, each of its edges is crossed at most once. We consider the following question: For any set P of n points in the plane, how many 1-plane Hamiltonian cycles can be packed into a complete geometric graph Kn? We investigate the problem by taking two different situations of P, namely, when P is in convex position, wheel configurations position. For points in general position we prove the lower bound of k − 1 where n = 2k + h and 0 ≤ h < 2k. In all of the situations, we investigate the constructions of the graphs obtained. Faculty of Sciences and Mathematics, University of Nis 2019 Article PeerReviewed text en http://psasir.upm.edu.my/id/eprint/81605/1/PLANE.pdf Trao, Hazim Michman and Ali, Niran Abbas and Chia, Gek L. and Kilicman, Adem (2019) Packing 1-plane Hamiltonian cycles in complete geometric graphs. Filomat, 33 (6). pp. 1561-1574. ISSN 2406-0933 http://journal.pmf.ni.ac.rs/filomat/index.php/filomat/article/view/6771 10.2298/FIL1906561T |
| spellingShingle | Trao, Hazim Michman Ali, Niran Abbas Chia, Gek L. Kilicman, Adem Packing 1-plane Hamiltonian cycles in complete geometric graphs |
| title | Packing 1-plane Hamiltonian cycles in complete geometric graphs |
| title_full | Packing 1-plane Hamiltonian cycles in complete geometric graphs |
| title_fullStr | Packing 1-plane Hamiltonian cycles in complete geometric graphs |
| title_full_unstemmed | Packing 1-plane Hamiltonian cycles in complete geometric graphs |
| title_short | Packing 1-plane Hamiltonian cycles in complete geometric graphs |
| title_sort | packing 1 plane hamiltonian cycles in complete geometric graphs |
| url | http://psasir.upm.edu.my/id/eprint/81605/1/PLANE.pdf |
| work_keys_str_mv | AT traohazimmichman packing1planehamiltoniancyclesincompletegeometricgraphs AT aliniranabbas packing1planehamiltoniancyclesincompletegeometricgraphs AT chiagekl packing1planehamiltoniancyclesincompletegeometricgraphs AT kilicmanadem packing1planehamiltoniancyclesincompletegeometricgraphs |