We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Almost all string graphs are intersection graphs of plane convex sets

Formal Metadata

Title
Almost all string graphs are intersection graphs of plane convex sets
Title of Series
Number of Parts
21
Author
Contributors
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
A {\em string graph} is the intersection graph of a family of continuous arcs in the plane. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of {\em almost all} string graphs on n vertices can be partitioned into {\em five} cliques such that some pair of them is not connected by any edge (n→∞). As a corollary, we obtain that {\em almost all} string graphs on n vertices are intersection graphs of plane convex sets.