Daniel Stefankovic (University of Chicago):
Recognizing String Graphs in NP
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. We show that string graphs can be recognized in NP.
The recognition problem was not known to be decidable until very
recently, when two independent papers established exponential
upper bounds on the number of intersections needed to realize a
string graph [PT'01,SS'01]. These results implied that the
recognition problem lies in NEXP. In the present paper we improve
this by showing that the recognition problem for string graphs is
in NP, and therefore NP-complete, since Kratochvil showed that
the recognition problem is NP-hard. The result has consequences
for the computational complexity of problems in graph drawing,
and topological inference.