Herbert Edelsbrunner, Günter Rote, and Emo Welzl:
Testing the necklace condition for shortest tours and optimal factors in
1. Theoretical Computer Science 66 (1989), 157-180, (MR #90i:90042).
2. In: "Automata, Languages, and Programming". Proceedings of the
14th International Colloquium on Automata, Languages, and Programming (ICALP),
Karlsruhe, Juli 1987. Editor: T. Ottmann. Lecture Notes in Computer Science
266, Springer-Verlag, 1987, pp. 364-375, (Zbl 636.68042, MR #88k:90065).
(This is a shortened and slightly modified version.)
A traveling salesman tour is a necklace tour if we can draw
disks with the given points as centers such that two
disks intersect if and only if the corresponding points are adjacent on the
If a necklace tour exists, it is the unique optimal tour.
We give an algorithm which tests in
whether a given tour is a necklace tour.
We give another algorithm which tests
in O(n2 log n) time and linear
space whether a necklace tour exists
for a given point set, by
the problem to a fractional 2-factor problem on a sparse bipartite graph.
Both algorithms can be generalized to m-factors of
point sets in the plane.
Note. In his dissertation,
solvable cases of the traveling salesman problem, Günter Rote has
time complexity of the algorithm for testing a given tour to
O(n3/2). The new algorithm is based on solving a system of
linear inequalities by the generalized nested dissection procedure of
Lipton, Rose, and Tarjan (1979).