| L01 | Oct. 20 | [+] Introduction and Basics |
[Notes] | [Video] |
|---|---|---|---|---|
| We first give an overview of the class and the topics covered. We then start with the basics. We give an alternative definition of a graph. We define embeddings, and duality | ||||
| L02 | Oct. 27 | [+] Basics II |
[Notes] | [Video] |
| We continue with basic definitions and properties. We recap the definition of embedding and duality, define and deletion and contractions of edges. We discuss basic connectivity properties of embedded graphs and their duals. We then define planar graphs and mention two important structural properties: interdigitating trees and duality of simple cuts and simple cycles. | ||||
| L03 | Nov. 3 | [+] Multiple Source Shortest Paths |
[Notes] | [Video] |
| We discuss an O(nlogn) time algorithm that, given a directed planar graph with dart lengths and a distinguished face f, computes a representation of all the shortest path trees rooted at vertices of f. The algorithm is based on interdigitating trees and uses dynamic trees to represent the trees efficiently. | ||||
| L04 | Nov. 10 | [+] Multiple Source Shortest Paths and Vector spaces |
[Notes] | [Video] |
| We finish the proof of correctness of the Multiple Source Shortest paths algorithm, and discuss various ways in which it can be used for reporting distances and shortest paths. We then begin to discuss vector spaces for graphs, which will be used to prove the cut-cycle duality and the existance of interdigitating trees. | ||||
| L05 | Nov. 17 | [+] Vector spaces and Separators |
[Notes] | [Video] |
| We use vector spaces for graphs to prove the duality of simple cycles and simple cuts, and the existence of interdigitationg trees. In the last part of the class we start discussing separators. Our discussion begins with showing the existence of a balanced edge separator for trees and of fundamental cycle separators for planar graphs. | ||||
| L06 | Nov. 24 | [+] Separators |
[Notes] | [Video] |
| We discuss a linear time algorithm for finding a small vertex separator in planar graphs. We then show an example of using such separators for finding maximum matchings. Finally, we start describing how to find small simple cycle separators in planar graphs. The algorithm builds on that of the vertex separator, but uses BFS levels in the face-vertex incidence graph (radial graph). | ||||
| L07 | Nov. 22 | [+] Cycle Separators & Shortest Paths with Negative Lengths |
[Notes] | [Video] |
| We finish the proof of the cycle separator algorithm. We then start discussing a nearly-linear time algorithm for shortest paths in the presence of negative lengths. We develop the overall structure of the algorithm, but do not get a nearly linear algorithm yet. We identify tht the bottleneck is running the Bellman-Ford algorithm on the dense distance graph - the complete graph on vertices of a cycle separator, where the length of an edge in the DDG corresponds to the length of a shortest path between its endpoints in the underlying planar graph. We show that implementing an iteration of Bellman-Ford can be cast into the problem of finding all column minima in the weighted incidence matrix of the DDG. We then introduce the Monge property, and show that we can find all column minima of a Monge matrix in time that is nearly linear in the number of rows. Finally we show that the weighted incidence matrix of the DDG can be decomposed into a small number of Monge matrices. | ||||
| L08 | Dec. 8 | [+] Shortest paths with negative lengths |
[Notes] | [Video] |
| We show that implementing an iteration of Bellman-Ford can be cast into the problem of finding all column minima in the weighted incidence matrix of the DDG. We then introduce the Monge property, and show that we can find all column minima of a Monge matrix in time that is nearly linear in the number of rows. Finally we show that the weighted incidence matrix of the DDG can be decomposed into a small number of Monge matrices. | ||||
| L09 | Dec. 15 | [+] Shortest Paths in Dense Distance Graphs |
[Notes] | [Video] |
| The topic of this lecture is an implementation of Dijkstra's algorithm on dense distance graphs, due to Fakcharoenphol and Rao. The running time is nearly linear in the number of vertices of the DDG, rather than in the number of edges as in a naive implementation of Dijkstra's algorithm. At the end of the lecture we start discussing exact distance oracles. | ||||
| L10 | Dec. 22 | [+] Branchwidth and Baker's approximation technique |
[Notes] | [Video] |
| The lecture starts with a breif discussion of problems from the second problem set. We then finish our short discussion of exact distance oracles by showing an oracle with nearly linear space and roughly squre-root query time. We present Baker's approximation scheme by showing its instantiation on the vertex cover problem. | ||||
| L11 | Dec. 29 | [+] Branch decomposition and Tamaki's theorem |
[Notes] | [Video] |
| We define carving and branch decompositions and show how to solve vertex cover using a dynamic program on the branch decomposition. Given a planar graph, we show how to find a carving decomposition whose width is related to the radius of the dual graph. We use this to prove Tamaki's theorem which shows (algorithmically) the existence of a branch decomposition whose width is roughly twice the minimum between the primal and dual radii. | ||||
| L12 | Jan. 5 | [+] PTAS for TSP in planar graphs |
[Notes] | [Video] |
| We describe an efficient PTAS for the travelling salesman problem in undirected planar graphs. | ||||
| L13 | Jan. 12 | [+] Circulations and maximum flow in st-planar graphs |
[Notes] | [Video] |
| We start our treatment of flow in planar graphs by relating circulations in the primal graph with face potentials in the planar dual. We show that the residual capacity of a dart with respect to a primal circulations is the slack cost of that dart in the dual with respect to the corresponding potential function. This establishes a connection between distances in the planar dual and capacity respecting circulations in the primal. We use this relation to give a linear-time algorithm for maximum st-flow when the source and sink lie on the same face. We conclide by briefly discussing a nearly linear-time algorithm for maximum st-flow in directed planar graphs. The algorithm resembles the MSSP algorithm. | ||||