Content deleted Content added
smallest non-string graph |
refactor; elaborate coloring hardness |
||
Line 18:
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|2010}}.</ref>
==Computational complexity==
{{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 (complexity)|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 polynomial-size 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}}▼
{{harvtxt|Ehrlich|Even|Tarjan|1976}} showed that testing whether a string graph is <math>k</math>-colorable is NP-complete, for every <math>k\ge 3</math>, and even when restricted to graphs with a given string representation consisting of straight line segments.{{sfnp|Ehrlich|Even|Tarjan|1976}}
==Other results==
The smallest graph that is not a string graph has 12 vertices.{{sfnp|Kratochvíl|Goljan|Kučera|1986}}
▲{{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}}
{{harvtxt|Kratochvíl|1991a}} observed that [[Graph minor#Induced minors|induced minors]] of string graphs are also string graphs. Induced minors are obtained from a given graph by contracting edges and deleting vertices; unlike the more general form of graph minor they do not allow deleting edges. For graph minors, the [[Robertson–Seymour theorem]] states that any graph property closed under minors has finitely many [[Forbidden graph characterization|minimal forbidden minors]]. However, this does not hold for induced minors, and Kratochvíl found an infinite family of minimal forbidden induced minors for string graphs.{{sfnp|Kratochvíl|1991a}}
| |||