| Abstract: |
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 reflects 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 (Pach,
Toth, and Schaefer, Stefankovic, 2001). 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 in 1991 that the
recognition problem is NP-hard. The result has consequences for the
computational complexity of problems in graph drawing, and topological
inference. |