Content deleted Content added
PLEASE STOP. You are not helping Wikipedia become better; you are only succeeding in annoying the editors who you should be enlisting to work with you. There is nothing wrong with these refs. |
related graph classes |
||
Line 4:
== 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 <math>5^{th}</math> 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 ==
Line 21 ⟶ 24:
| 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
| |||