Drawing Hamiltonian cycles with no large angles
Summary: Let \(n \geq 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\). \textit{S. P. Fekete} and \textit{G. J. Woeginger} [Comput. Geom. 8, No. 4, 195--218 (1997; Zbl 1133.90385)] 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\).
- Drawing Hamiltonian cycles with no large angles
- Hamiltonian cycles in planar triangulations with no separating triangles
- Hamilton cycles in planar graphs and Venn diagrams
- scientific article; zbMATH DE number 3912424
- scientific article; zbMATH DE number 568821
- Hamilton cycles in plane triangulations
- Hamiltonian Paths and Cycles in Planar Graphs
- Hamiltonian cycles in polyhedral maps
- Hamilton Cycles in Oriented Graphs
- scientific article; zbMATH DE number 5901724
- Bounded-angle minimum spanning trees
- Angle-restricted tours in the plane.
- Drawing Hamiltonian cycles with no large angles
- Going around in circles
- On the number of similar instances of a pattern in a finite set
- Bounded-angle spanning tree: modeling networks with angular constraints
- Intersecting diametral balls induced by a geometric graph
- Intersecting ellipses induced by a max-sum matching
- Acute tours in the plane
- Acute tours in the plane
- Noncrossing longest paths and cycles
- Noncrossing longest paths and cycles
This page was built for publication: Drawing Hamiltonian cycles with no large angles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q426910)
