**Next:** Problem 54: Traveling Salesman Problem in Solid Grid Graphs

**Previous:** Problem 52: Queue-Number of Planar Graphs

- Statement
What is the complexity of finding a cycle-cover of a planar grid graph that has the fewest possible 90^\circ turns? (An 180^\circ U-turn counts as two turns.) A

*planar grid graph*is a graph whose vertices are any set of points on the planar integer lattice and whose edges connect every pair of vertices at unit distance.- Origin
Aggarwal et al. [ACK+97] show that the more general problem of finding a cycle cover for a planar set of points that minimizes total turn angle is NP-hard. Arkin et al. [ABD+01], [ABD+05] consider the problem in grid graphs, but are only able to give approximations.

- Status/Conjectures
Solved: proved NP-hard by Fekete and Krupke [FK19]

- Motivation
Minimizing turns is a natural geometric measure; understanding its algorithmic behavior is of general interest.

- Partial and Related Results
[ABD+01], [ABD+05] show that the problem is polynomially solvable when restricted to

*thin*grid graphs, i.e., grid graphs that do not contain an induced 2 \times 2 square. For this special case, the problem behaves somewhat similarly to a Chinese Postman Problem. The problem of finding a minimum-turn tour is shown to be NP-complete, even for this special case.In 2019, Fekete and Krupke [FK19] established that finding a minimum-turn cycle cover in a planar grid graph is NP-hard, thereby providing an answer to this problem.

- Related Open Problems
Minimum-turn cycle cover in a “solid” (genus-zero) grid graph: What is the complexity of finding a minimum-turn tour for a given planar grid graph without holes?

TSP in a solid grid graph: What is the complexity of finding a minimum-length tour for a given planar grid graph without holes? (Problem 54)

- Appearances
- Categories
traveling salesman; optimization; point sets; graphs

- Entry Revision History
S. P. Fekete, 12 Dec. 2003; D. Krupke, 29 Nov. 2023

- [ABD+01]
E. M. Arkin, M. A. Bender, E. D. Demaine, S. P. Fekete, J. S. B. Mitchell, and S. Sethia. Optimal covering tours with turn costs. In

*Proc. 13th ACM-SIAM Sympos. Discrete Algorithms*, pages 138–147, 2001.- [ABD+05]
E. M. Arkin, M. A. Bender, E. D. Demaine, S. P. Fekete, J. S. B. Mitchell, and S. Sethia. Optimal covering tours with turn costs.

*SIAM Journal on Computing*, 35(3):531–566, 2005.- [ACK+97]
Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, and Baruch Schieber. The angular-metric traveling salesman problem. In

*Proc. 8thh Annual ACM-SIAM Sympos. Discrete Algorithms*, pages 221–229, January 1997.- [FK19]
Sándor P. Fekete and Dominik Krupke. Covering tours and cycle covers with turn costs: Hardness and approximation. In

*Proceedings of the 11th International Conference on Algorithms and Complexity*, volume 11485 of*Lecture Notes in Computer Science*, pages 224–236, Rome, Italy, May 2019.