Flows, cuts, and string graphs via metric geometry

by · Jul 23, 2016 · 474 views ·

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.

Watch SlidesLive on mobile devices

© SlidesLive Inc.