Packing 1-Plane Hamiltonian Cycles in Complete Geometric Graphs

Hazim Michman Trao

Published 2016-11-28Version 1

A relaxation for problems in plane geometric graphs is to allow the geometric graphs to be 1-plane. Counting the number of Hamiltonian cycles that are contained in a geometric graph is {\bf \#P}-complete even if the graph is known to be planar \cite{lot:refer}. We consider the problem of backing edge-disjoint 1-plane Hamiltonian cycles in a complete geometric graph $K_{|P|}$ on any set $P$ of $n$ points in general position in the plane. We prove that there are at least $k-1$ sets of 1-plane Hamiltonian cycles that can be packed into $K_{|P|}$, where $n=2^{k}+h$ and $0\leq h <2^{k}$. We also give bounds for the problem in some special configurations.