Packing 1-Plane Hamiltonian Cycles in Complete Geometric Graphs

2016/11/28 by Trao, Hazim Michman
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1611.09096

Abstract

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 \citelot:refer. 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 K_n\/? 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=2^k+h\/ and 0≤ h <2^k\/. In all of the situations, we investigate the constructions of the graphs obtained.

Related

• Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique
• On plane cycles in geometric multipartite graphs
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• Using SAT to study plane Hamiltonian substructures in simple drawings
• Plane Hamiltonian Cycles in Convex Drawings