Title: Decidability of String Graphs
Published: September 2000
Authors: Marcus SchaeferDaniel Štefankovic
Abstract: We show that string graphs can be recognized in nondeterministic 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 Kratochvil and Matousek and settles the long-standing open problem of the decidability of string graph recognition (Sinden, Graham).
Full Paper: [postscript]