Flows, cuts, and string graphs via metric geometry

Jul 23, 2016

Speakers

About

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.

Organizer

Categories

About The Mathematics of Jiří Matoušek

International Conference on The Mathematics of Jiří Matoušek, Charles University, Prague 2016

Store presentation

Should this presentation be stored for 1000 years?

How do we store presentations

Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%

Sharing

Recommended Videos

Presentations on similar topic, category or speaker

Interested in talks like this? Follow The Mathematics of Jiří Matoušek