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
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>
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á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>.
J. Pach, B. Reed, Y. Yuditsky, Discrete and Computational Geometry 63 (2020) 888–917.
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.
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>
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>.
79622020-06-14T22:00:51Z2021-01-12T08:16:15Z