Drawing Hamiltonian cycles with no large angles

Let n >= 4 be even. It is shown that every set S of n points in the plane can be connected by a (possibly self-intersecting) spanning tour (Hamiltonian cycle) consisting of n straight-line edges such that the angle between any two consecutive edges is at most 2 pi/3. For n = 4 and 6, this statement is tight. It is also shown that every even-element point set S can be partitioned into at most two subsets, S-1 and S-2, each admitting a spanning tour with no angle larger than pi/2. Fekete and Woeginger conjectured that for sufficiently large even n, every n-element set admits such a spanning tour. We confirm this conjecture for point sets in convex position. A much stronger result holds for large point sets randomly and uniformly selected from an open region bounded by finitely many rectifiable curves: for any epsilon > 0, these sets almost surely admit a spanning tour with no angle larger than epsilon.

Published in:
Graph Drawing , 3-14
Presented at:
Graph Drawing
Berlin, Springer-Verlag

 Record created 2010-10-06, last modified 2018-01-28

Rate this document:

Rate this document:
(Not yet reviewed)