{{harvtxt|Benzer|1959}} described a concept similar to string graphs as they applied to genetic structures. Later, {{harvtxt|Sinden|1966}} specified the same idea to electrical networks and printed circuits. ThroughThe mathematical study of string graphs began through a collaboration between Sinden and Graham, and the characterization of string graphs eventually came to be posed as an open question at the <math>5^{th}</math> Hungarian Colloquium on Combinatorics in 1976 and .<ref>{{harvtxtcitation|Ehrlich|Even|TarjanGraham|1976}}.</ref> showedHowever, computingthe theirrecognition chromatic number to be '''NP'''-hard. {{harvtxt|Kratochvil|1991}} looked atof string graphs andwas foundeventually thatproven theyto formbe an induced minor closed class[[NP-complete]], butimplying notthat ano minorsimple closedcharacterization classis oflikely graphs.to The problem of recognizing string graphs is '''NP'''-completeexist.<ref>{{harvtxt|Kratochvil|1991}} showed string graph recognition to be NP-hard, but were not able to show that it could be solved in NP. After intermediate results by {{harvtxt|Schaefer|Štefankovič|2001}} and {{harvtxt|Pach|Tóth|2002}}, {{harvtxt|Schaeffer|Sedgwick|Štefankovič|2003}} completed the proof that the problem is NP-complete.</ref>
{{harvtxt|Ehrlich|Even|Tarjan|1976}} showed computing their chromatic number to be '''NP'''-hard. {{harvtxt|Kratochvil|1991}} looked at string graphs and found that they form an induced minor closed class, but not a minor closed class of graphs.
