In this talk we show that string graphs can be recognized in NP, a result which has consequences for the computational complexity of problems in graph drawing, and topological inference (Euler diagrams).A string graph is the intersection graph of a set of curves in the plane. Each curve is represented by a vertex, and an edge between two vertices means that the corresponding curves intersect. Determining the complexity of recognising string graphs has been an open problem for at least thirty years.
The talk is based on a new techreport by Marcus Schaefer, Eric Sedgwick, and Daniel Stefankovic.