| Title: |
Decidability of String Graphs |
| Authors: | Marcus Schaefer, Daniel Stefankovič |
| 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: | [ps] |