[+]
Graph Problems. Vertex Cover: planar maxdegree3; exact vertex cover (polynomial), edge cover (polynomial), connected vertex cover, rectilinear Steiner tree. Vertex Coloring: planar maxdegree4 3coloring, maxdegree3 3coloring (polynomial), Push1X, Push1G (gravity). Graph Orientation: 1in3, 2in3, 0or3 vertices; packing trominoes. Graph Layout: Bandwidth, minimum linear arrangement, cutwidth, vertex separation, sum cut, edge bisection, vertex bisection; bipartite crossing number, crossing number, Rubik's Cube. 
[Scribe Notes] [src]  
This lecture is our last about straightup NPhardness. We've already seen the main techniques for such proofs, but there are a few other techniques that get used now and then. We will see three:

Handwritten notes, page 1/7 •
[previous page] •
[next page] •
[PDF]
Handwritten notes, page 1/7 • [previous page] • [next page] • [PDF] 

Slides, page 1/31 •
[previous page] •
[next page] •
[PDF]
http://dx.doi.org/10.1137/0211025 Slides, page 1/31 • [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.