String graph: Difference between revisions

Revision as of 04:55, 26 October 2009

Revision as of 06:32, 26 October 2009

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 5<mathsup>5^{th}</mathsup> 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|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|Schaefer|Sedgwick|Štefankovič|2003}} completed the proof that the problem is NP-complete.</ref>

==Related graph classes==