Geometric Graph Theory

David Eppstein, Computer Science 295, Spring 2007

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

Tentative list of topics:

• 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
• Injective metric spaces and tight spans.
• Tight spans of planar partial cubes and related graphs.
• 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₁ distances
• Graph separators. Planar graph separators. Leighton and Rao's approximate separators via Bourgain's theorem.
• Bourgain's theorem: approximate L₁ embedding of metrics.