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