String graphs. II: Recognizing string graphs is NP-hard (Q1112845): Difference between revisions

A graph is called a string graph if it is isomorphic to the intersection graph of a system of Jordan curves in the plane. It has been a long standing open problem whether string graphs can be recognized in polynomial time. Here we prove that recognizing string graphs and some related problems are NP-hard.