Content deleted Content added
Dedhert.Jr (talk | contribs) →Background: benzer I meant |
expand NP membership and describe why it was difficult |
||
Line 5:
== 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.{{sfnp|Benzer|1959}} Later, {{harvtxt|Sinden|1966}} specified the same idea to [[electrical network]]s and printed circuits.{{sfnp|Sinden|1966}} 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|Ehrlich|Even|Tarjan|1976}}, {{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.
==Related graph classes==
Line 20:
==Other results==
{{harvtxt|Ehrlich|Even|Tarjan|1976}} showed computing the [[chromatic number]] of string graphs to be NP-hard.{{sfnp|Ehrlich|Even|Tarjan|1976}}
{{harvtxt|Ehrlich|Even|Tarjan|1976}} showed computing the [[chromatic number]] of string graphs to be NP-hard.{{sfnp|Ehrlich|Even|Tarjan|1976}} {{harvtxt|Kratochvil|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 Kratochvil found an infinite family of minimal forbidden induced minors for string graphs.{{sfnp|Kratochvil|1991a}}▼
{{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|
Analogously to the [[planar separator theorem]], every <math>m</math>-edge string graph can be partitioned into two subsets, each a constant fraction the size of the whole graph, by the removal of <math>O(m^{3/4}\log^{1/2}m)</math> vertices. It follows that the [[Biclique-free graph|biclique-free]] string graphs, string graphs containing no <math>K_{t,t}</math> subgraph for some constant <math>t</math>, have <math>O(n)</math> edges and more strongly have [[bounded expansion|polynomial expansion]].<ref>{{harvtxt|Fox|Pach|2010}}; {{harvtxt|Dvořák|Norin|2016}}.</ref>
Line 92 ⟶ 95:
| year = 1976}}.
*{{citation
| first = Jan | last =
| title = String Graphs. I. The number of critical nonstring graphs is infinite
| journal = [[Journal of Combinatorial Theory, Series B]]
| year = 1991a
| volume = 52
Line 102 ⟶ 105:
}}.
*{{citation
| first = Jan | last =
| title = String Graphs. II. Recognizing string graphs is NP-Hard
| journal = [[Journal of Combinatorial Theory, Series B]]
| year = 1991b
| volume = 52
Line 111 ⟶ 114:
| issue = 1| doi-access = free
}}.
*{{citation
| last1 = Kratochvíl | first1 = Jan | author1-link = Jan Kratochvíl
| last2 = Matoušek | first2 = Jiří | author2-link = Jiří Matoušek (mathematician)
| doi = 10.1016/0095-8956(91)90050-T
| issue = 1
| journal = [[Journal of Combinatorial Theory, Series B]]
| mr = 1122293
| pages = 1–4
| title = String graphs requiring exponential representations
| volume = 53
| year = 1991}}.
*{{citation
| first = L. | last = Lovász | authorlink = László Lovász
| |||