A lower bound for the optimal crossing-free Hamiltonian cycle problem (Q1091399)

Consider a drawing in the plane of \(K_ n\), the complete graph on n vertices. If all edges are restricted to be straight line segments, the drawing is called rectilinear. Consider a Hamiltonian cycle in a drawing of \(K_ n\). If no pair of the edges of the cycle cross, it is called a crossing-free Hamiltonian cycle (cfhc). Let \(\Phi\) (n) represent the maximum number of cfhc's of any drawing of \(K_ n\), and \(\Phi\) (n) the maximum number of cfhc's of any rectilinear drawing of \(K_ n\). The problem of determining \(\Phi\) (n) and \({\bar \Phi}\)(n), and determining which drawings have this many cfhc's, is known as the optimal cfhc problem. We present a brief survey of recent work on this problem, and then, employing a recursive counting argument based on computer enumeration, we establish a substantially improved lower bound for \(\Phi\) (n) and \({\bar \Phi}\)(n). In particular, it is shown that \({\bar \Phi}\)(n) is at least \(k\times 3.2684^ n\). We conjecture that both \(\Phi\) (n) and \({\bar \Phi}\)(n) are at most \(c\times 4.5^ n\).