# Geometric approximation algorithms

by Sariel Har-Peled.
This is the webpage for the book Geometric approximation algorithms that is published by the AMS.

Here some addiontal notes/chapters that were written after the book publication. These are all early versions with many many many many many typos, but hopefully they should be helpful to somebody out there (maybe):

## Planar graphs

1. Planar graphs: Basic definitions, Jordan theorem (without proof), straightline embedding, Kuratowski theorem (without proof), planarity testing algorithm.
2. Grid embedding: Canonical ordering, grid embedding using canonical ordering, breaking a trinagulations into trees (i.e., realizers), grid embedding using realizers.
3. Circle packing theorem: the game of whac-an-angle, proof.
4. Planar separator: Separator from circle packing, a linear time separator algorithm, Extensions: Cycle separtor, weights, separating a cluster.

## Other stuff

1. Pack & Prune: Nice distance problems, linear time approximation algorithm.
2. Fréchet distance: Exact algorithm, c-packed curves, approximation algorithm.