**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] consider the problem in grid graphs, but are only able to give approximations.

- Status/Conjectures
Open.

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

- Partial and Related Results
[ABD+01] 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 known to be NP-complete, even for this special case.More recent details and related problems can be found in the version [ABD+03].

- 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.

- [ABD+01]
E. M. Arkin, M. A. Bender, E. 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+03]
E. M. Arkin, M. A. Bender, E. Demaine, S. P. Fekete, J. S. B. Mitchell, and S. Sethia. Optimal covering tours with turn costs. Manuscript (submitted), 2003.

- [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.