We address the problem of wallpapering a room so as to minimize the paper wasted. We show that the problem is equivalent to finding a shortest hamiltonian chain in a highly structured graph. When the chain connects two equivalent nodes traveling salesman problem, the "nearest-neighbor" technique yields an optimal solution.
['Robert S. Garfinkel']
Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems