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 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 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 Annual Symposium on the Theory of Computing (STOC 2002).
