@article{7962,
abstract = {A string graph is the intersection graph of a family of continuous arcs in the plane. The intersection graph of a family of plane convex sets is a string graph, but not all string graphs can be obtained in this way. 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→∞). We also show that every graph with the above property is an intersection graph of plane convex sets. As a corollary, we obtain that almost all string graphs on n vertices are intersection graphs of plane convex sets.},
author = {Pach, János and Reed, Bruce and Yuditsky, Yelena},
issn = {14320444},
journal = {Discrete and Computational Geometry},
number = {4},
pages = {888--917},
publisher = {Springer Nature},
title = {{Almost all string graphs are intersection graphs of plane convex sets}},
doi = {10.1007/s00454-020-00213-z},
volume = {63},
year = {2020},
}