Background
Seymour Benzer (1959) described a concept similar to string graphs as they applied to genetic structures. In that context, he also posed the specific case of intersecting intervals on a line, namely the now classical family of interval graphs. Later, Sinden (1966) specified the same idea to electrical networks and printed circuits. The mathematical study of string graphs began with the paper Ehrlich, Even & Tarjan (1976) and through a collaboration between Sinden and Ronald Graham, where the characterization of string graphs eventually came to be posed as an open question at the 5th Hungarian Colloquium on Combinatorics in 1976. However, the recognition of string graphs was eventually proven to be NP-complete, implying that no simple characterization is likely to exist.
Read more about this topic: String Graph
Famous quotes containing the word background:
“Pilate with his question “What is truth?” is gladly trotted out these days as an advocate of Christ, so as to arouse the suspicion that everything known and knowable is an illusion and to erect the cross upon that gruesome background of the impossibility of knowledge.”
—Friedrich Nietzsche (1844–1900)
“... every experience in life enriches one’s background and should teach valuable lessons.”
—Mary Barnett Gilson (1877–?)
“In the true sense one’s native land, with its background of tradition, early impressions, reminiscences and other things dear to one, is not enough to make sensitive human beings feel at home.”
—Emma Goldman (1869–1940)