ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Consider a drawing in the plane ofK n , the complete graph onn vertices. If all edges are restricted to be straight line segments, the drawing is called rectilinear. Consider a Hamiltonian cycle in a drawing ofK n . If no pair of the edges of the cycle cross, it is called a crossing-free Hamiltonian cycle (cfhc). Let Φ(n) represent the maximum number of cfhc's of any drawing ofK n , and $$\bar \Phi$$ (n) the maximum number of cfhc's of any rectilinear drawing ofK n . The problem of determining Φ(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 Φ(n) and $$\bar \Phi$$ (n). In particular, it is shown that $$\bar \Phi$$ (n) is at leastk × 3.2684 n . We conjecture that both Φ(n) and $$\bar \Phi$$ (n) are at mostc × 4.5 n .
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02187887
Permalink
