Alternating Hamilton Cycles with Minimum Number of Crossings in the Plane.

Let X and Y be two disjoint sets of points in the plane such that X = Y and no three points of X ∪ Y are on the same line. Then we can draw an alternating Hamilton cycle on X U Y in the plane which passes through alternately points of X and those of Y, whose edges are straight-line segments, and which contains at most X - 1 crossings. Our proof gives an O(n² logn) time algorithm for finding such an alternating Hamilton cycle, where n = X. Moreover we show that the above upper bound X - 1 on crossing number is best possible for some configurations. [ABSTRACT FROM AUTHOR]