Almost all string graphs are intersection graphs of plane convex sets
Pach, János
Reed, Bruce
Yuditsky, Yelena
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.
Springer Nature
2020
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.app.ist.ac.at/record/7962
Pach J, Reed B, Yuditsky Y. Almost all string graphs are intersection graphs of plane convex sets. <i>Discrete and Computational Geometry</i>. 2020;63(4):888-917. doi:<a href="https://doi.org/10.1007/s00454-020-00213-z">10.1007/s00454-020-00213-z</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/s00454-020-00213-z
info:eu-repo/semantics/altIdentifier/issn/01795376
info:eu-repo/semantics/altIdentifier/issn/14320444
info:eu-repo/semantics/altIdentifier/arxiv/1803.06710
info:eu-repo/grantAgreement/FWF//Z00342
info:eu-repo/semantics/openAccess