String graph

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.

[1] However, the recognition of string graphs was eventually proven to be NP-complete, implying that no simple characterization is likely to exist.

Alternatively, by the circle packing theorem, any planar graph may be represented as a collection of circles, any two of which cross if and only if the corresponding vertices are adjacent; these circles (with a starting and ending point chosen to turn them into open curves) provide a string graph representation of the given planar graph.

Scheinerman's conjecture, now proven, is the even stronger statement that every planar graph may be represented by the intersection graph of straight line segments, a very special case of strings.

[4] Ehrlich, Even & Tarjan (1976) showed computing the chromatic number of string graphs to be NP-hard.