| [+] Hamiltonicity. Icosian game, planar directed max-degree-3, planar bipartite max-degree-3, max-degree-3 square grid graphs, triangle grid graphs, hex grid graphs, unit orthogonal segment intersection graphs. Euclidean degree-3 MST, Settlers of Catan mate-in-0, 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 NP-hard: 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] |
