String graph: Difference between revisions

Revision as of 19:28, 3 May 2014

Revision as of 23:04, 22 March 2015

Line 3:

== Background ==

{{harvs|txt|last=Benzer|first=Seymour|authorlink=Seymour Benzer|year=1959}} 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|19911991b}} showed string graph recognition to be NP-hard, but werewas 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==

Line 18:

==Other results==

{{harvtxt|Ehrlich|Even|Tarjan|1976}} showed computing the chromatic number of string graphs to be NP-hard. {{harvtxt|Kratochvil|19911991a}} found that string graphs form an induced minor closed class, but not a minor closed class of graphs.

==Notes==

Line 70:

| year = 1976}}.

*{{citation

| first = Jan | last = Kratochvil | authorlink = Jan Kratochvíl

| title = String Graphs. I. The number of critical nonstring graphs is infinite

| journal = Journal of Combinatorial Theory, Series B

| year = 19911991a

| volume = 52

| pages = 53–66

Line 79:

| issue = 1}}.

*{{citation

| first = Jan | last = Kratochvil | authorlink = Jan Kratochvíl

| title = String Graphs. II. Recognizing string graphs is NP-Hard

| journal = Journal of Combinatorial Theory, Series B

| year = 19911991b

| volume = 52

| pages = 67–78