Algorithms for planar graphs and surface graphs
Lunes 10 y martes 11 a las 3PM (90min.)
I will describe several fundamental structural and algorithmic results for planar graphs and surface graphs. These classes of graphs have been fertile ground for algorithms research for decades, both because they naturally model networks that arise in practice, and because they admit simpler and faster algorithms than more general graphs. Specific topics include fast algorithms for minimum spanning trees, straight-line embeddings, separators, shortest paths, and shortest topologically interesting cycles. No prior experience with topology will be required.
(I will assume some familiarity with graphs and algorithms, but not with topology.)