Revision as of 20:53, 25 October 2009 edit David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,811 edits more refactor ← Previous edit		Revision as of 20:53, 25 October 2009 edit undo David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,811 edits wrong template Next edit →
Line 2: == Background == {{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. The 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.<ref>{{~~citation~~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\|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> ==Related graph classes==

String graph: Difference between revisions