ChapterZero

I just came across the initial lecture for a course on spectral graph theory that did a great job of illustrating how interesting the graph laplacian is. You might’ve heard of the Fiedler vector– its magical properties are what I was searching for an explanation for–, but did you know that the top two eigenvectors of planar graphs (sometimes, most of the time?) form the coordinates of nice planar embeddings? In the same vein, the bottom eigenvectors can provide good colorings. Two incredible facts that have yet to be explained.

The video lectures that inspired.me to look up spectral graph theory are pretty interesting in their own right. The first explained a simple but apparently powerful technique for edge-preserving image smoothing based on the heat equation on graphs. The second was about a seed-based technique for image segmentation based on random walks on graphs– this looks very powerful, but the lecturer is awfully boring; it may be more interesting to just peruse his publications.