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

In 1959, 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 Elrich, Even, and Tarjan (1976) showed computing the chromatic number to be NP-hard. Kratochvil (1991) looked at string graphs and found that they form an induced minor closed class, but not a minor closed class of graphs and that the problem of recognizing string graphs is NP-hard. Schaeffer and Stefankovic (2002) found this problem to be NP-complete.

Related graph classes

Every planar graph is a string graph; Scheinerman's conjecture 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) harvtxt error: no target: CITEREFChalopinGonçalvesOchem2007 (help) 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. And 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.

References

• S. Benzer (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.
• F. W. Sinden (1966). "Topology of thin film RC-circuits". Bell System Technical Journal: 1639--1662.
• 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. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
• R. L. Graham (1976). "Problem 1". Open Problems at 5th Hungarian Colloquium on Combinatorics. {{cite journal}}: Unknown parameter |country= ignored (help)
• G. Elrich and S. Even and R.E. Tarjan (1976). "Intersection graphs of curves in the plane". Journal of Combinatorial Theory. 21.
• Jan Kratochvil (1991). "String Graphs I: The number of critical non-string graphs is infinite". Journal of Combinatorial Theory B. 51 (2).
• Jan Kratochvil (1991). "String Graphs II: Recognizing String Graphs is NP-Hard". Journal of Combinatorial Theory B. 52 (1): 67--78. {{cite journal}}: Unknown parameter |month= ignored (help)
• Marcus Schaefer and Daniel Stefankovic (2001). "Decidability of string graphs". Proceedings of the ${\displaystyle 33^{rd}}$  Annual ACM Symposium on the Theory of Computing (STOC 2001): 241--246.
• Janos Pach and Geza Toth (2002). "Recognizing String Graphs is Decidable". Discrete and Computational Geometry. 28: 593--606.
• Marcus Schaefer and Eric Sedgwick and Daniel Stefankovic (2002). "Recognizing String Graphs in NP". Proceedings of the ${\displaystyle 33^{th}}$  Annual Symposium on the Theory of Computing (STOC 2002).