a. Dense distance graphs
b. Improving Dijkstra to O(n log log n) time
c. Repricing
d. Nested dissection
e. Monge arrays and SMAWK
f. Planar distances are (almost) Monge)
g. Shortest paths with negative edge lengths in O(n log^2 n) time.