Revision as of 20:44, 20 June 2018 edit Bibcode Bot (talk \| contribs) Bots 42,789 edits m Adding 0 arxiv eprint(s), 1 bibcode(s) and 0 doi(s). Did it miss something? Report bugs, errors, and suggestions at User talk:Bibcode Bot ← Previous edit		Revision as of 19:42, 14 July 2018 edit undo 2402:3a80:b24:4e6a:5c52:2e40:142f:5213 (talk) →Background Next edit →
Line 2: == Background == {{harvs\|txt\|last=Benzer\|first=Seymour\|authorlink=Seymour Benzer\|year=~~1959~~2001}} described a concept similar to string graphs as they applied to genetic structures. In that context, he also posed the specific case of intersecting intervals on a line, namely the now classical family of [[interval graph]]s. Later, {{harvtxt\|Sinden\|1966}} specified the same idea to electrical networks and printed circuits. The mathematical study of string graphs began with the paper {{harvtxt\|Ehrlich\|Even\|Tarjan\|1976}} and through a collaboration between Sinden and [[Ronald Graham]], where the characterization of string graphs eventually came to be posed as an open question at the 5th Hungarian Colloquium on Combinatorics in 1976.<ref>{{harvtxt\|Graham\|1976}}.</ref> However, the recognition of string graphs was eventually proven to be [[NP-complete]], implying that no simple characterization is likely to exist.<ref>{{harvtxt\|Kratochvil\|1991b}} showed string graph recognition to be NP-hard, but was 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\|Schaefer\|Sedgwick\|Štefankovič\|2003}} completed the proof that the problem is NP-complete.</ref>

String graph: Difference between revisions