The course will meet Monday and Wednesdays, 3:30 - 4:50, in CS 259. Grading will be attendance-based.

- Introduction: what is a geometric graph?
- Euclidean distances
- Reconstructing point placements from distances
- Combinatorial rigidity; pebble games and data structures.
- Unfolding linkages.
- Dilation of planar graphs.
- Length-based optimization of planar graphs: min spanning tree, min dilation spanning tree, min diameter spanning tree, min max edge length triangulation.
- Min weight triangulation. MWT hardness and MWT approximation.
- Hamming distances
- Partial cubes from line arrangements. Approximate embedding of Euclidean distances into partial cubes. Examples of partial cubes.
- Characterization of and recognition of partial cubes
- Partial cubes and flip graphs of triangulations (dept. seminar talk)
- Lattice embedding, face-symmetric planar graphs, and graph drawing of partial cubes
- L
_{∞}distances - Tree distances
- Ultrametrics and hierarchical clustering.
- Framework for probabilistic embedding in trees. Karp's 1989 2-approximation of cycle graph metrics.
- Approximation algorithms based on tree embeddings: metric labeling, K-median clustering.
- Equivalence of Steiner and non-Steiner tree embedding.
- Optimal probabilistic embedding in trees.
- L
_{1}distances - Graph separators. Planar graph separators. Leighton and Rao's approximate separators via Bourgain's theorem.
- Bourgain's theorem: approximate L
_{1}embedding of metrics.