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 boolean OR Y are on the same line. Then we can draw an alternating Hamilton cycle on X boolean OR 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(2) log n) 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.
hamilton cycle plane crossing number two point sets line embedding