2017
06.01

I posted some new class notes on planar graphs. Naturally they contain typos etc, but hopefully they would be useful for somebody out there (or not). Anyway, they are available at the bottom of this page. The notes currently cover (i) planarity checking, (ii) grid embedding, (iii) circle packing theorem, and (iv) planar separator.

  1. Another easy way to see that planarity checking is in polynomial time is by reducing to solving linear system over GF(2), through the Hanani-Tutte Theorem.