The ACO Seminar (2012-2013)

A string graph is a graph that can be obtained as the intersection graph of curves (strings) in the plane. Despite much attention over the past half century, the structure of string graphs is poorly understood. The incomparability graph of a partially ordered set (P,<) has vertex set P and two elements of P are adjacent if and only if they are incomparable. It is known that every incomparability graph is a string graph, and that the converse is not true. Nevertheless, we demonstrate an intimate relationship between these two types of graphs: we prove that for every collection C of curves in the plane whose intersection graph is dense, we can pick for each curve s in C a subcurve s' such that the intersection graph of the collection of curves s' is a dense incomparability graph. It follows that every dense string graph has a dense subgraph which is an incomparability graph. Utilizing this connection between arrangements of curves and partially ordered sets, we make progress on several extremal problems for string graphs and crossing edge patterns in graphs drawn in the plane. Joint work with Janos Pach.