String graph

In the mathematical area of graph theory, a string graph is an intersection graph of strings in a plane. Given a graph $G$, $G$ is a string graph if and only if there exists a set of curves, or strings, that permit a drawing in the plane where no three strings intersect at the same point and the set of strings that intersect is isomorphic to $E(G)$. That is, a string graph is an intersection graph of curves in the plane where each curve is a vertex and each intersection an edge.

More formally, $G$ is a string graph if and only if there exists some set of strings $S$ such that the intersection graph

$I=(\{s|s\in S\},\{(s,t)|s,t\in S\wedge s\cap t\not =\phi \})$

is isomorphic to $G$. We say that the size of a string graph is equal to the number of intersections, $|I|$.

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 $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.

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.
• 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 $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 $33^{th}$ Annual Symposium on the Theory of Computing (STOC 2002).