Content deleted Content added
→Related graph classes: math |
smallest non-string graph |
||
Line 20:
==Other results==
The smallest graph that is not a string graph has 12 vertices.{{sfnp|Kratochvíl|Goljan|Kučera|1986}}
{{harvtxt|Ehrlich|Even|Tarjan|1976}} showed computing the [[chromatic number]] of string graphs to be NP-hard.{{sfnp|Ehrlich|Even|Tarjan|1976}}
{{harvtxt|Kratochvíl|1991b}} showed string graph recognition to be NP-hard, but was not able to show that it could be solved in NP.{{sfnp|Kratochvíl|1991b}} One barrier to solving the problem in NP is that, for some string graphs, all systems of curves that realize the graph have an exponential number of crossings, so an explicit realization cannot be used as a witness for the graph being a string graph.{{sfnp|Kratochvíl|Matoušek|1991}} Instead, subsequent research in this area focused on compressed descriptions of realizations in terms of the sequences of crossings on each string, described using the theory of [[formal language]]s. 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 in NP, and therefore is NP-complete.{{sfnp|Schaefer|Sedgwick|Štefankovič|2003}}
Line 114 ⟶ 116:
| issue = 1| doi-access = free
}}.
*{{citation
| last1 = Kratochvíl | first1 = Jan | author1-link = Jan Kratochvíl
| last2 = Goljan | first2 = Miroslav
| last3 = Kučera | first3 = Petr
| issue = 3
| journal = Rozpravy Československé Akad. Věd Řada Mat. Přírod. Věd
| mr = 865778
| page = 96
| title = String graphs
| volume = 96
| year = 1986}}.
*{{citation
| last1 = Kratochvíl | first1 = Jan | author1-link = Jan Kratochvíl
| |||