Almost all string graphs are intersection graphs of plane convex sets
Lena Yuditsky (BGU)
Tuesday, November 27, 2018, 15:45 – 16:45, 201
Please Note the Unusual Time and Place!
A 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 almost all string graphs on $n$ vertices can be partitioned into five cliques such that some pair of them is not connected by any edge ($n\rightarrow\infty$). As a corollary, we obtain that 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.