article
Almost all string graphs are intersection graphs of plane convex sets
published
yes
János
Pach
author E62E3130-B088-11EA-B919-BF823C25FEA4
Bruce
Reed
author
Yelena
Yuditsky
author
HeEd
department
The Wittgenstein Prize
project
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 Nature2020
eng
Discrete and Computational Geometry
01795376
14320444
1803.0671010.1007/s00454-020-00213-z
634888-917
J. Pach, B. Reed, and Y. Yuditsky, “Almost all string graphs are intersection graphs of plane convex sets,” <i>Discrete and Computational Geometry</i>, vol. 63, no. 4. Springer Nature, pp. 888–917, 2020.
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>
J. Pach, B. Reed, Y. Yuditsky, Discrete and Computational Geometry 63 (2020) 888–917.
Pach, János, Bruce Reed, and Yelena Yuditsky. “Almost All String Graphs Are Intersection Graphs of Plane Convex Sets.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2020. <a href="https://doi.org/10.1007/s00454-020-00213-z">https://doi.org/10.1007/s00454-020-00213-z</a>.
Pach, János, et al. “Almost All String Graphs Are Intersection Graphs of Plane Convex Sets.” <i>Discrete and Computational Geometry</i>, vol. 63, no. 4, Springer Nature, 2020, pp. 888–917, doi:<a href="https://doi.org/10.1007/s00454-020-00213-z">10.1007/s00454-020-00213-z</a>.
Pach, J., Reed, B., & Yuditsky, Y. (2020). Almost all string graphs are intersection graphs of plane convex sets. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href="https://doi.org/10.1007/s00454-020-00213-z">https://doi.org/10.1007/s00454-020-00213-z</a>
Pach J, Reed B, Yuditsky Y. 2020. Almost all string graphs are intersection graphs of plane convex sets. Discrete and Computational Geometry. 63(4), 888–917.
79622020-06-14T22:00:51Z2021-01-12T08:16:15Z