String graph

In graph theory, a string graph is an intersection graph of curves in the plane; each curve is called a "string". Given a graph G, G is a string graph if and only if there exists a set of curves, or strings, drawn in the plane such that no three strings intersect at a single point and such that the graph having a vertex for each curve and an edge for each intersecting pair of curves is isomorphic to G.

Background

Benzer (1959) described a concept similar to string graphs as they applied to genetic structures. Later, Sinden (1966) specified the same idea to electrical networks and printed circuits. The mathematical study of string graphs began through a collaboration between Sinden and Graham, and the characterization of string graphs eventually came to be posed as an open question at the ${\displaystyle 5^{th}}$  Hungarian Colloquium on Combinatorics in 1976.^[1] However, the recognition of string graphs was eventually proven to be NP-complete, implying that no simple characterization is likely to exist.^[2]

Ehrlich, Even & Tarjan (1976) showed computing their chromatic number to be NP-hard. Kratochvil (1991) harvtxt error: multiple targets (2×): CITEREFKratochvil1991 (help) looked at string graphs and found that they form an induced minor closed class, but not a minor closed class of graphs.

Related graph classes

Every planar graph is a string graph; Scheinerman's conjecture, now proven, states that every planar graph may be represented by the intersection graph of straight line segments, which are a very special case of strings, and 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. Every circle graph, as an intersection graph of line segments, 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. The complement graph of every comparability graph is also a string graph.^[3]

Notes

1. {{citation}}: Empty citation (help).
2. Kratochvil (1991) harvtxt error: multiple targets (2×): CITEREFKratochvil1991 (help) showed string graph recognition to be NP-hard, but were not able to show that it could be solved in NP. After intermediate results by Schaefer & Štefankovič (2001) and Pach & Tóth (2002), Schaeffer, Sedgwick & Štefankovič (2003) harvtxt error: no target: CITEREFSchaefferSedgwickŠtefankovič2003 (help) completed the proof that the problem is NP-complete.
3. Golumbic, Rotem & Urrutia (1983) and Lovász (1983) harvtxt error: no target: CITEREFLovász1983 (help). See also Fox & Pach (2009).

References

• Benzer, S. (1959), "On the topology of the genetic fine structure", Proceedings of the National Academy of Sciences of the United States of America, 45: 1607–1620, doi:10.1073/pnas.45.11.1607.
• 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.
• 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.
• Fox, J.; Pach, J. (2009), String graphs and incomparability graphs (PDF).
• Graham, R. L. (1976), "Problem 1", Open Problems at 5th Hungarian Colloquium on Combinatorics {{citation}}: Unknown parameter |country= ignored (help).
• 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.
• Kratochvil, Jan (1991), "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.
• Kratochvil, Jan (1991), "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.
• Lovász,, L. (1983), "Perfect graphs", Selected Topics in Graph Theory, vol. 2, London: Academic Press, pp. 55–87.
• Pach, János; Tóth, Geza (2002), "Recognizing string graphs is decidable", Discrete and Computational Geometry, 28: 593--606, doi:10.1007/s00454-002-2891-4.
• Schaefer, Marcus; Štefankovič, Daniel (2001), "Decidability of string graphs", Proceedings of the 33^rd Annual ACM Symposium on the Theory of Computing (STOC 2001): 241--246.
• Schaefer, Marcus; Sedgwick, Eric; Štefankovič, Daniel (2003), "Recognizing string graphs in NP", Journal of Computer and System Sciences, 67 (2): 365–380, doi:10.1016/S0022-0000(03)00045-X.
• Sinden, F. W. (1966), "Topology of thin film RC-circuits", Bell System Technical Journal, 45: 1639–1662.