@article{4084,
abstract = {A tour of a finite set P of points is a necklace-tour if there are disks with the points in P as centers such that two disks intersect if and only if their centers are adjacent in . It has been observed by Sanders that a necklace-tour is an optimal traveling salesman tour.
In this paper, we present an algorithm that either reports that no necklace-tour exists or outputs a necklace-tour of a given set of n points in O(n2 log n) time. If a tour is given, then we can test in O(n2) time whether or not this tour is a necklace-tour. Both algorithms can be generalized to ƒ-factors of point sets in the plane. The complexity results rely on a combinatorial analysis of certain intersection graphs of disks defined for finite sets of points in the plane.},
author = {Herbert Edelsbrunner and Rote,Günter and Welzl, Emo},
journal = {Theoretical Computer Science},
number = {2},
pages = {157 -- 180},
publisher = {Elsevier},
title = {{Testing the necklace condition for shortest tours and optimal factors in the plane}},
doi = {10.1016/0304-3975(89)90133-3},
volume = {66},
year = {1989},
}