### Packing 1-Plane Hamiltonian Cycles in Complete Geometric Graphs

#### Abstract

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 of points in the plane, how many 1-plane Hamiltonian cycles can be packed into a complete geometric graph ? We investigate the problem by taking two different situations of , namely, when is in convex position, wheel configurations position. For points in general position we prove the lower bound of where and . In all of the situations, we investigate the constructions of the graphs obtained.

### Refbacks

- There are currently no refbacks.