We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Alternating Hamilton Cycles with Minimum Number of Crossings in the Plane.
- Authors
Kaneko, Atsushi; Kano, M.; Yoshimoto, Kiyoshi; Asano, T.
- Abstract
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.
- Subjects
HAMILTONIAN systems; DIFFERENTIABLE dynamical systems
- Publication
International Journal of Computational Geometry & Applications, 2000, Vol 10, Issue 1, p73
- ISSN
0218-1959
- Publication type
Article
- DOI
10.1142/S021819590000005X