Content deleted Content added
smallest non-string graph |
m Open access bot: hdl updated in citation with #oabot. |
||
| (8 intermediate revisions by 3 users not shown) | |||
Line 15:
If every edge of a given graph <math>G</math> is [[Subdivision (graph theory)|subdivided]], the resulting graph is a string graph if and only if <math>G</math> is planar. In particular, the subdivision of the [[complete graph]] <math>K_5</math> shown in the illustration is not a string graph, because <math>K_5</math> is not planar.<ref name="ss-s"/>
Every [[circle graph]], as an intersection graph of line segments (the chords of a circle), 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.{{sfnp|Kratochvíl|1991a|pp=56–57}}
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}} and {{harvtxt|Fox|Pach|2012}}.</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}} 3-colorings of string graphs, when they exist, can be found in the subexponential time bound <math>2^{O(n^{2/3}\log n)}</math>, but a similarly fast time for more colors is unlikely, under standard complexity-theoretic assumptions: an algorithm for 4-coloring in time <math>2^{o(n)}</math> would contradict the [[exponential time hypothesis]].{{sfnp|Bonnet|Rzążewski|2019}}
==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}}
Line 45 ⟶ 47:
| pmid=16590553
| pmc=222769| doi-access = free }}.
*{{citation
| last1 = Bonnet | first1 = Édouard
| last2 = Rzążewski | first2 = Paweł
| doi = 10.1007/s00453-019-00568-7
| issue = 7
| journal = Algorithmica
| mr = 3948280
| pages = 3047–3073
| title = Optimality program in segment and string graphs
| volume = 81
| year = 2019| doi-access = free
}}.
*{{citation
| last1 = Chalopin | first1 = J. | last2 = Gonçalves | first2 = D. | last3 = Ochem | first3 = P.
Line 83 ⟶ 97:
| year = 2010| s2cid = 5705145 | url = http://infoscience.epfl.ch/record/152985 }}.
*{{citation
| last2 = Pach | first2 = János | author2-link = János Pach
| doi = 10.1016/j.aim.2012.03.011
| issue = 3
| journal = Advances in Mathematics
| mr = 2921183
| pages = 1381–1401
| title = String graphs and incomparability graphs
| volume = 230
| year = 2012| hdl = 1721.1/98834
| hdl-access = free
}}.
*{{citation
| first1 = M. C. | last1 = Golumbic |author1-link = Martin Charles Golumbic | first2 = D. | last2 = Rotem | first3 = J. | last3 = Urrutia | author3-link = Jorge Urrutia Galicia
| title = Comparability graphs and intersection graphs
| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
| |||