String graph

<h2 id="background">Background</h2>
<a href="/facts/Seymour_Benzer/Hz4EKm67">Seymour Benzer</a> (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 <a href="/facts/Interval_graph/oLwYI3uT">interval graphs</a>. Later, Sinden (1966) specified the same idea to <a href="/facts/Electrical_network/zt94kTW0">electrical networks</a> and printed circuits. The mathematical study of string graphs began with the paper Ehrlich, Even & Tarjan (1976) and 
through a collaboration between Sinden and <a href="/facts/Ronald_Graham/ukKzczTL">Ronald Graham</a>, where the characterization of string graphs eventually came to be posed as an open question at the 5th Hungarian Colloquium on Combinatorics in 1976.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> However, the recognition of string graphs was eventually proven to be <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>, implying that no simple characterization is likely to exist.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>

<h2 id="related-graph-classes">Related graph classes</h2>

Every <a href="/facts/Planar_graph/plREagr9">planar graph</a> is a string graph:<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> one may form a string graph representation of an arbitrary plane-embedded graph by drawing a string for each vertex that loops around the vertex and around the midpoint of each adjacent edge, as shown in the figure. For any edge uv of the graph, the strings for u and v cross each other twice near the midpoint of uv, and there are no other crossings, so the pairs of strings that cross represent exactly the adjacent pairs of vertices of the original planar graph. Alternatively, by the <a href="/facts/Circle_packing_theorem/EPMq7roF">circle packing theorem</a>, any planar graph may be represented as a collection of circles, any two of which cross if and only if the corresponding vertices are adjacent; these circles (with a starting and ending point chosen to turn them into open curves) provide a string graph representation of the given planar graph. Chalopin, Gonçalves & Ochem (2007) proved that every planar graph has a string representation in which each pair of strings has at most one crossing point, unlike the representations described above.
<a href="/facts/Scheinerman%27s_conjecture/EdhsUr2b">Scheinerman's conjecture</a>, now proven, is the even stronger statement that every planar graph may be represented by the intersection graph of straight line segments, a very special case of strings.

If every edge of a given graph G is <a href="/facts/Subdivision_(graph_theory)/WbFo1mNW">subdivided</a>, the resulting graph is a string graph if and only if G is planar. In particular, the subdivision of the <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> K5 shown in the illustration is not a string graph, because K5 is not planar.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
Every <a href="/facts/Circle_graph/mI27LMXp">circle graph</a>, as an intersection graph of line segments (the chords of a circle), is also a string graph. Every <a href="/facts/Chordal_graph/7hNerUdA">chordal graph</a> 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.
The <a href="/facts/Complement_graph/IdHUPFr3">complement graph</a> of every <a href="/facts/Comparability_graph/dLht35EJ">comparability graph</a> is also a string graph.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

<h2 id="other-results">Other results</h2>
Ehrlich, Even & Tarjan (1976) showed computing the chromatic number of string graphs to be NP-hard.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> Kratochvil (1991a) found that string graphs form an induced minor closed class, but not a minor closed class of graphs. Unlike for minor closed classes, where the <a href="/facts/Robertson%E2%80%93Seymour_theorem/J7g4CJ74">Robertson–Seymour theorem</a> states that there can be only finitely many <a href="/facts/Forbidden_graph_characterization/50Kex6JU">minimal forbidden minors</a>, Kratochvil found an infinite family of minimal forbidden induced minors for string graphs.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
Every 
 
 
 
 m
 
 
 {\displaystyle m}
 
-edge string graph can be partitioned into two subsets, each a constant fraction the size of the whole graph, by the removal of 
 
 
 
 O
 (
 
 m
 
 3
 
 /
 
 4
 
 
 
 log
 
 1
 
 /
 
 2
 
 
 ⁡
 m
 )
 
 
 {\displaystyle O(m^{3/4}\log ^{1/2}m)}
 
 vertices. It follows that the <a href="/facts/Biclique-free_graph/Dyb7xHPK">biclique-free string graphs</a>, string graphs containing no 
 
 
 
 
 K
 
 t
 ,
 t
 
 
 
 
 {\displaystyle K_{t,t}}
 
 subgraph for some constant 
 
 
 
 t
 
 
 {\displaystyle t}
 
, have 
 
 
 
 O
 (
 n
 )
 
 
 {\displaystyle O(n)}
 
 edges and more strongly have <a href="/facts/Bounded_expansion/9Dv8GYp9">polynomial expansion</a>.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h2 id="notes">Notes</h2>

<ul><li><a href="/facts/Seymour_Benzer/Hz4EKm67">Benzer, S.</a> (1959), "On the topology of the genetic fine structure", <a href="/facts/Proceedings_of_the_National_Academy_of_Sciences_of_the_United_States_of_America/w75CThX0">Proceedings of the National Academy of Sciences of the United States of America</a>, 45 (11): 1607–1620, <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1959PNAS...45.1607B">1959PNAS...45.1607B</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1073%2Fpnas.45.11.1607">10.1073/pnas.45.11.1607</a>, <a href="/facts/PMC_(identifier)/dX1zMt71">PMC</a> <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC222769">222769</a>, <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/16590553">16590553</a>.</li>
<li>Chalopin, J.; Gonçalves, D.; Ochem, P. (2007), "Planar graphs are in 1-STRING", Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM and SIAM, pp. 609–617.</li>
<li><a href="/facts/Zden%C4%9Bk_Dvo%C5%99%C3%A1k/5JIfIyK0">Dvořák, Zdeněk</a>; Norin, Sergey (2016), "Strongly sublinear separators and polynomial expansion", <a href="/facts/SIAM_Journal_on_Discrete_Mathematics/7BG23qL5">SIAM Journal on Discrete Mathematics</a>, 30 (2): 1095–1101, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1504.04821">1504.04821</a>, <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2015arXiv150404821D">2015arXiv150404821D</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F15M1017569">10.1137/15M1017569</a>.</li>
<li>Ehrlich, G.; Even, S.; <a href="/facts/Robert_Tarjan/kn1pMCN0">Tarjan, R. E.</a> (1976), "Intersection graphs of curves in the plane", <a href="/facts/Journal_of_Combinatorial_Theory/oYS6G76K">Journal of Combinatorial Theory</a>, 21 (1): 8–20, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0095-8956%2876%2990022-8">10.1016/0095-8956(76)90022-8</a>.</li>
<li><a href="/facts/Jacob_Fox/BK7IhhV3">Fox, Jacob</a>; <a href="/facts/J%C3%A1nos_Pach/x1t8LFL7">Pach, János</a> (2010), <a href="http://infoscience.epfl.ch/record/152985">"A separator theorem for string graphs and its applications"</a>, <a href="/facts/Combinatorics,_Probability_and_Computing/lyqhr4XT">Combinatorics, Probability and Computing</a>, 19 (3): 371, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1017%2Fs0963548309990459">10.1017/s0963548309990459</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:5705145">5705145</a>.</li>
<li>Golumbic, M.; Rotem, D.; <a href="/facts/Jorge_Urrutia_Galicia/wTDb6uJ0">Urrutia, J.</a> (1983), "Comparability graphs and intersection graphs", <a href="/facts/Discrete_Mathematics_(journal)/K4e6z8wQ">Discrete Mathematics</a>, 43 (1): 37–46, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0012-365X%2883%2990019-5">10.1016/0012-365X(83)90019-5</a>.</li>
<li><a href="/facts/Ronald_Graham/ukKzczTL">Graham, R. L.</a> (1976), "Problem 1", Open Problems at 5th Hungarian Colloquium on Combinatorics.</li>
<li><a href="/facts/Jan_Kratochv%C3%ADl/BQ5Has54">Kratochvil, Jan</a> (1991a), "String Graphs. I. The number of critical nonstring graphs is infinite", Journal of Combinatorial Theory, Series B, 52 (1): 53–66, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0095-8956%2891%2990090-7">10.1016/0095-8956(91)90090-7</a>.</li>
<li><a href="/facts/Jan_Kratochv%C3%ADl/BQ5Has54">Kratochvil, Jan</a> (1991b), "String Graphs. II. Recognizing string graphs is NP-Hard", Journal of Combinatorial Theory, Series B, 52 (1): 67–78, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0095-8956%2891%2990091-W">10.1016/0095-8956(91)90091-W</a>.</li>
<li><a href="/facts/L%C3%A1szl%C3%B3_Lov%C3%A1sz/X0VB38Ee">Lovász, L.</a> (1983), "Perfect graphs", Selected Topics in Graph Theory, vol. 2, London: Academic Press, pp. 55–87.</li>
<li><a href="/facts/J%C3%A1nos_Pach/x1t8LFL7">Pach, János</a>; Tóth, Geza (2002), "Recognizing string graphs is decidable", <a href="/facts/Discrete_%26_Computational_Geometry/wVPxzUWo">Discrete & Computational Geometry</a>, 28 (4): 593–606, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs00454-002-2891-4">10.1007/s00454-002-2891-4</a>.</li>
<li>Schaefer, Marcus; Štefankovič, Daniel (2001), "Decidability of string graphs", <a href="/facts/Symposium_on_Theory_of_Computing/xsemn7kG">Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing (STOC 2001)</a>: 241–246.</li>
<li>Schaefer, Marcus; Sedgwick, Eric; Štefankovič, Daniel (2003), "Recognizing string graphs in NP", Journal of Computer and System Sciences, 67 (2): 365–380, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0022-0000%2803%2900045-X">10.1016/S0022-0000(03)00045-X</a>.</li>
<li>Sinden, F. W. (1966), "Topology of thin film RC-circuits", Bell System Technical Journal, 45 (9): 1639–1662, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2Fj.1538-7305.1966.tb01713.x">10.1002/j.1538-7305.1966.tb01713.x</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Graham (1976). - Graham, R. L. (1976), "Problem 1", Open Problems at 5th Hungarian Colloquium on Combinatorics <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Kratochvil (1991b) showed string graph recognition to be NP-hard, but was not able to show that it could be solved in NP. After intermediate results by Schaefer & Štefankovič (2001) and Pach & Tóth (2002), Schaefer, Sedgwick & Štefankovič (2003) completed the proof that the problem is NP-complete. - Kratochvil, Jan (1991b), "String Graphs. II. Recognizing string graphs is NP-Hard", Journal of Combinatorial Theory, Series B, 52 (1): 67–78, doi:10.1016/0095-8956(91)90091-W <a href="https://doi.org/10.1016%2F0095-8956%2891%2990091-W" target="_blank">https://doi.org/10.1016%2F0095-8956%2891%2990091-W</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Schaefer & Štefankovič (2001) credit this observation to Sinden (1966). - Schaefer, Marcus; Štefankovič, Daniel (2001), "Decidability of string graphs", Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing (STOC 2001): 241–246 <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Schaefer & Štefankovič (2001) credit this observation to Sinden (1966). - Schaefer, Marcus; Štefankovič, Daniel (2001), "Decidability of string graphs", Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing (STOC 2001): 241–246 <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Golumbic, Rotem & Urrutia (1983) and Lovász (1983). See also Fox & Pach (2010). - Golumbic, M.; Rotem, D.; Urrutia, J. (1983), "Comparability graphs and intersection graphs", Discrete Mathematics, 43 (1): 37–46, doi:10.1016/0012-365X(83)90019-5 <a href="https://doi.org/10.1016%2F0012-365X%2883%2990019-5" target="_blank">https://doi.org/10.1016%2F0012-365X%2883%2990019-5</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Ehrlich, Even & Tarjan (1976). - Ehrlich, G.; Even, S.; Tarjan, R. E. (1976), "Intersection graphs of curves in the plane", Journal of Combinatorial Theory, 21 (1): 8–20, doi:10.1016/0095-8956(76)90022-8 <a href="https://doi.org/10.1016%2F0095-8956%2876%2990022-8" target="_blank">https://doi.org/10.1016%2F0095-8956%2876%2990022-8</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Kratochvil (1991a). - Kratochvil, Jan (1991a), "String Graphs. I. The number of critical nonstring graphs is infinite", Journal of Combinatorial Theory, Series B, 52 (1): 53–66, doi:10.1016/0095-8956(91)90090-7 <a href="https://doi.org/10.1016%2F0095-8956%2891%2990090-7" target="_blank">https://doi.org/10.1016%2F0095-8956%2891%2990090-7</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Fox & Pach (2010); Dvořák & Norin (2016). - Fox, Jacob; Pach, János (2010), "A separator theorem for string graphs and its applications", Combinatorics, Probability and Computing, 19 (3): 371, doi:10.1017/s0963548309990459, S2CID 5705145 <a href="http://infoscience.epfl.ch/record/152985" target="_blank">http://infoscience.epfl.ch/record/152985</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
</ol>

String graph open-in-new

String graph