[+] Hamiltonicity. Icosian game, planar directed maxdegree3, planar bipartite maxdegree3, maxdegree3 square grid graphs, triangle grid graphs, hex grid graphs, unit orthogonal segment intersection graphs. Euclidean degree3 MST, Settlers of Catan matein0, Slitherlink, Hashiwokakero. Milling, lawn mowing, 3D printing, minimum turns.  [Scribe Notes] [src]  
This lecture is about Hamiltonicity (paths/cycles that visit every vertex exactly once). In particular, we'll see a very special and useful case that is NPhard: grid graphs, defined by a set of points on a grid, with edges exactly when two points have unit distance. This version is hard for square, triangular, and hexagonal grids. We'll prove this and see how to reduce to other fun problems like optimally mowing your lawn, 3D printing, Settlers of Catan, and Nikoli puzzles Slitherlink and Hashiwokakero. 
Handwritten notes, page 1/7 •
[previous page] •
[next page] •
[PDF]
Handwritten notes, page 1/7 • [previous page] • [next page] • [PDF] 

Slides, page 1/37 •
[previous page] •
[next page] •
[PDF]
http://puzzlemuseum.com/month/picm02/200207icosian.htm Slides, page 1/37 • [previous page] • [next page] • [PDF] 
The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The handwritten notes and slides should advance automatically. If you have any trouble with playback, email Erik.