Drawing Hamiltonian Cycles with No Large Angles

Dumitrescu, Adrian and Pach, János and Tóth, Géza (2010) Drawing Hamiltonian Cycles with No Large Angles. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009 , pp. 3-14(Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_3).

Full text not available from this repository.


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π/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, S1 and S2 , each admitting a spanning tour with no angle larger than π/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 ε > 0, these sets almost surely admit a spanning tour with no angle larger than ε.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-11805-0_3
Classifications: Z Theory > Z.250 Geometry
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1078

Actions (login required)

View Item View Item