23. Červenec 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
Pro uložení prezentace do věčného trezoru hlasovalo 0 diváků, což je 0.0 %
Prezentace na podobné téma, kategorii nebo přednášejícího