String graph: Difference between revisions

Revision as of 20:52, 25 October 2009

Revision as of 20:53, 25 October 2009

Line 3:

== 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|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>

{{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.

==Related graph classes==

Every [[planar graph]] is a string graph; [[Scheinerman's conjecture]], now proven, states that every planar graph may be represented by the intersection graph of straight line segments, which are a very special case of strings, and {{harvtxt|Chalopin|Gonçalves|Ochem|2007}} proved that every planar graph has a string representation in which each pair of strings has at most one crossing point. Every [[circle graph]], as an intersection graph of line segments, is also a string graph. Every [[chordal graph]] may be represented as a string graph: chordal graphs are intersection graphs of subtrees of trees, and one may form a string representation of a chordal graph by forming a planar embedding of the corresponding tree and replacing each subtree by a string that traces around the subtree's edges. The [[complement graph]] of every [[comparability graph]] is also a string graph.<ref>{{harvtxt|Golumbic|Rotem|Urrutia|1983}} and {{harvtxt|Lovász|1983}}. See also {{harvtxt|Fox|Pach|2009}}.</ref>

==Other results==

{{harvtxt|Ehrlich|Even|Tarjan|1976}} showed computing theirthe chromatic number of string graphs 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.

==Notes==