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∪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.