2013/11/20 by Jiří Matoušek, Matoušek, Jiří
Computer Science · Mathematics · #05C62 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #cs.CG #math.CO #msc:05C62
paper · pdf · doi:10.48550/arxiv.1311.5048
Expository paper based on course notes
arxiv created 2014/04/25 · arxiv updated 2014/08/10
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 the pair-crossing number. For the existence of small separators, unwrapping the complete proof include generally useful results on approximate flow-cut dualities.