pith. sign in

arxiv: 1803.06710 · v1 · pith:GUGXC2IAnew · submitted 2018-03-18 · 🧮 math.CO · cs.CG

Almost all string graphs are intersection graphs of plane convex sets

classification 🧮 math.CO cs.CG
keywords graphgraphsstringintersectionplaneconvexsetsalmost
0
0 comments X
read the original abstract

A {\em 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 {\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\rightarrow\infty$). We also show that every graph with the above property is an intersection graph of plane convex sets. As a corollary, we obtain that {\em almost all} string graphs on $n$ vertices are intersection graphs of plane convex sets.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.