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. Through a collaboration between Sinden and Graham, 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 and 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. The problem of recognizing string graphs is NP-complete.^[1]

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.^[2]

Notes

1. 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.
2. 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.