Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1142/S021819590000005X | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS |
Keywords | DocType | Volume |
two point sets, plane, crossing number, Hamilton cycle, line embedding | Journal | 10 |
Issue | ISSN | Citations |
1 | 0218-1959 | 8 |
PageRank | References | Authors |
0.83 | 2 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Atsushi Kaneko | 1 | 169 | 24.21 |
| Mikio Kano | 2 | 548 | 99.79 |
| Kiyoshi Yoshimoto | 3 | 133 | 22.65 |