Almost all string graphs are intersection graphs of plane convex sets
Lena Yuditsky · Open Collections · 2018
A {\em string graph} is the intersection graph of a family of continuous arcs in the plane. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of {\em almost all} string graphs on $n$ vertices can be partitioned into {\em five} cliques such that some pair of them is not connected by any edge ($n\rightarrow\infty$). As a corollary, we obtain that {\em almost all} string graphs on $n$ vertices are intersection graphs of plane convex sets. This is a joint work with Janos Pach and Bruce Reed.