Planar Graphs in 2 1/2 Dimensions
Presented at Theory Lunch, Carnegie Mellon University, March 18, 2009
In 1864, James Clerk Maxwell published his now famous correspondence between equilibrium stresses and liftings of planar graphs into 3D "terrains." We will explore this classic theorem and how it has influenced many areas of modern theoretical computer science. This survey will touch on results in graph drawing, regular triangulations, network routing, rigidity theory, and spectral graph theory (time permitting).