String graphs and incomparability graphs

Fox, Jacob and Pach, János (2012) String graphs and incomparability graphs. ADVANCES IN MATHEMATICS, 230 (3). pp. 1381-1401. ISSN 0001-8708

Preview

Text stringpartial071709.pdf Download (334kB) | Preview

Abstract

Given a collection C of curves in the plane, its string graph is defined as the graph with vertex set C, in which two curves in C are adjacent if and only if they intersect. Given a partially ordered set (P, <), its incomparability graph is the graph with vertex set P, in which two elements of P are adjacent if and only if they are incomparable. It is known that every incomparability graph is a string graph. For "dense" string graphs, we establish a partial converse of this statement. We prove that for every ε>0 there exists δ>0 with the property that if C is a collection of curves whose string graph has at least ε{pipe}C{pipe} 2 edges, then one can select a subcurve γ ' of each γ∈C such that the string graph of the collection {γ ':γ∈C} has at least δ{pipe}C{pipe} 2 edges and is an incomparability graph. We also discuss applications of this result to extremal problems for string graphs and edge intersection patterns in topological graphs.

Actions (login required)

Edit Item