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:
“Silence is the universal refuge, the sequel to all dull discourses and all foolish acts, a balm to our every chagrin, as welcome after satiety as after disappointment; that background which the painter may not daub, be he master or bungler, and which, however awkward a figure we may have made in the foreground, remains ever our inviolable asylum, where no indignity can assail, no personality can disturb us.”
—Henry David Thoreau (1817–1862)
“They were more than hostile. In the first place, I was a south Georgian and I was looked upon as a fiscal conservative, and the Atlanta newspapers quite erroneously, because they didn’t know anything about me or my background here in Plains, decided that I was also a racial conservative.”
—Jimmy Carter (James Earl Carter, Jr.)
“I had many problems in my conduct of the office being contrasted with President Kennedy’s conduct in the office, with my manner of dealing with things and his manner, with my accent and his accent, with my background and his background. He was a great public hero, and anything I did that someone didn’t approve of, they would always feel that President Kennedy wouldn’t have done that.”
—Lyndon Baines Johnson (1908–1973)