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

* cite journal
author = S. Benzer
title = On the topology of the genetic fine structure
journal = Proceedings of the National Academy of Sciences of the United States of America
volume = 45
year = 1959
pages = 1607--1620
doi = 10.1073/pnas.45.11.1607
* cite journal
journal = Bell System Technical Journal
title = Topology of thin film RC-circuits
author = F. W. Sinden
year = 1966
pages = 1639--1662
*cite conference
author = Chalopin, J.; Gonçalves, D.; Ochem, P.
title = Planar graphs are in 1-STRING
booktitle = Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms
publisher = ACM and SIAM
year = 2007
pages = 609–617
* cite journal
author = R. L. Graham
title = Problem 1
journal = Open Problems at 5th Hungarian Colloquium on Combinatorics
country = Hungary
year = 1976
* cite journal
author = G. Elrich and S. Even and R.E. Tarjan
title = Intersection graphs of curves in the plane
journal = Journal of Combinatorial Theory
volume = 21
year = 1976
* cite journal
author = Jan Kratochvil
title = String Graphs I: The number of critical non-string graphs is infinite
journal = Journal of Combinatorial Theory B
year = 1991
volume = 51
number = 2
* cite journal
author = Jan Kratochvil
title = String Graphs II: Recognizing String Graphs is NP-Hard
journal = Journal of Combinatorial Theory B
year = 1991
volume = 52
number = 1
month = May
pages = 67--78
doi = 10.1016/0095-8956(91)90091-W
* cite journal
author = Marcus Schaefer and Daniel Stefankovic
title = Decidability of string graphs
journal = Proceedings of the $33^\{rd\}$ Annual ACM Symposium on the Theory of Computing (STOC 2001)
year = 2001
pages = 241--246
* cite journal
journal = Discrete and Computational Geometry
title = Recognizing String Graphs is Decidable
author = Janos Pach and Geza Toth
volume = 28
pages = 593--606
year = 2002
doi = 10.1007/s00454-002-2891-4
* cite journal
author = Marcus Schaefer and Eric Sedgwick and Daniel Stefankovic
title = Recognizing String Graphs in NP
journal = Proceedings of the $33^\{th\}$ Annual Symposium on the Theory of Computing (STOC 2002)
year = 2002