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 [18, 20]. 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 Kratochvíl [12] showed that the recognition problem is NP -hard. The result has consequences for the computational complexity of problems in graph drawing, and topological inference.

Authors

• Marcus Schaefer 0001
• Eric Sedgwick
• Daniel Stefankovic

Keywords

No keywords are indexed for this paper.