Jul 23, 2016
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.
International Conference on The Mathematics of Jiří Matoušek, Charles University, Prague 2016
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Presentations on similar topic, category or speaker