String graphs and separators
2016
String graphs, that is, intersection graphs of curves in the plane, have been studied since the 1960s. We provide an expository presentation of several results, including very recent ones: some string graphs require an exponential number of crossings in every string representation; exponential number is always sufficient; string graphs have small separators; and the current best bound on the crossing number of a graph in terms of pair-crossing number. For the existence of small separators, the proof includes generally useful results on approximate flow-cut dualities. This expository paper was prepared as a material for two courses co-taught by the author in 2013, at Charles University and at ETH Zurich. It aims at a complete and streamlined presentation of several results concerning string graphs. This important and challenging class of intersection graphs has tradi-tionally been studied at the Department of Applied Mathematics of the Charles University, especially by Jan Kratochv́ıl and his students and collaborators.