Almost all string graphs are intersection graphs of plane convex sets

J. Pach, B. Reed, Y. Yuditsky, Discrete and Computational Geometry 63 (2020) 888–917.


Journal Article | Published | English

Scopus indexed
Author
Pach, JánosIST Austria; Reed, Bruce; Yuditsky, Yelena
Department
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.
Publishing Year
Date Published
2020-06-05
Journal Title
Discrete and Computational Geometry
Volume
63
Issue
4
Page
888-917
ISSN
eISSN
IST-REx-ID

Cite this

Pach J, Reed B, Yuditsky Y. Almost all string graphs are intersection graphs of plane convex sets. Discrete and Computational Geometry. 2020;63(4):888-917. doi:10.1007/s00454-020-00213-z
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. https://doi.org/10.1007/s00454-020-00213-z
Pach, János, Bruce Reed, and Yelena Yuditsky. “Almost All String Graphs Are Intersection Graphs of Plane Convex Sets.” Discrete and Computational Geometry 63, no. 4 (2020): 888–917. https://doi.org/10.1007/s00454-020-00213-z.
J. Pach, B. Reed, and Y. Yuditsky, “Almost all string graphs are intersection graphs of plane convex sets,” Discrete and Computational Geometry, vol. 63, no. 4, pp. 888–917, 2020.
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ános, et al. “Almost All String Graphs Are Intersection Graphs of Plane Convex Sets.” Discrete and Computational Geometry, vol. 63, no. 4, Springer Nature, 2020, pp. 888–917, doi:10.1007/s00454-020-00213-z.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1803.06710

Search this title in

Google Scholar