We show that string graphs can be recognized in non-deterministic exponential time by giving an exponential upper bound on the number of intersections for a drawing realizing the string graph in the plane. This upper bound confirms a conjecture by Kratochvíl and Matoušek and settles the long-standing open problem of the decidability of string graph recognition. Finally we show how to apply the result to solve another old open problem: deciding the existence of Euler diagrams, a central problem of topological inference.
The paper is online as DePaul technical report TR00-005.ps.