A string graph is the intersection graph of continuous arcs in the plane. Matoušek showed that every string graph with m edges has a balanced separator with O(√m . log(m)) vertices. Fox and Pach have conjectured that the correct bound is O(√m). and this would be optimal if true. We modify Jirka's argument to confirm their conjecture.

- #Euclidean distortion problem
- #Euclidean space
- #finite metric spaces
- #Jiří Matoušek
- #Mathematics
- #metrics
- #Sparsest Cut problem

© SlidesLive Inc.