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, such that the graph having a vertex for each curve and an edge for each intersecting pair of curves is isomorphic to G.
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.
Related graph classes
Every planar graph is a string graph: one may form a string graph representation of an arbitrary plane-embedded graph by drawing a string for each vertex that loops around the vertex and around the midpoint of each adjacent edge, as shown in the figure. For any edge u v {\displaystyle uv} of the graph, the strings for u {\displaystyle u} and v {\displaystyle v} cross each other twice near the midpoint of u v {\displaystyle uv} , and there are no other crossings, so the pairs of strings that cross represent exactly the adjacent pairs of vertices of the original planar graph. 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. 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, unlike the representations described above. 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.
If every edge of a given graph G {\displaystyle G} is subdivided, the resulting graph is a string graph if and only if G {\displaystyle G} is planar. In particular, the subdivision of the complete graph K 5 {\displaystyle K_{5}} shown in the illustration is not a string graph, because K 5 {\displaystyle K_{5}} is not planar. Every circle graph, as an intersection graph of line segments (the chords of a circle), is also a string graph. 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. The complement graph of every comparability graph (also known as the cocomparability graph) is also a string graph.
Computational complexity Kratochvíl (1991b) showed string graph recognition to be NP-hard, but was not able to show that it could be solved in NP. One barrier to solving the problem in NP is that, for some string graphs, all systems of curves that realize the graph have an exponential number of crossings, so an explicit realization cannot be used as a polynomial-size witness for the graph being a string graph. Instead, subsequent research in this area focused on compressed descriptions of realizations in terms of the sequences of crossings on each string, described using the theory of formal languages. After intermediate results by Schaefer & Štefankovič (2001) and Pach & Tóth (2002), Schaefer, Sedgwick & Štefankovič (2003) completed the proof that the problem is in NP, and therefore is NP-complete. Ehrlich, Even & Tarjan (1976) showed that testing whether a string graph is k {\displaystyle k} -colorable is NP-complete, for every k ≥ 3 {\displaystyle k\geq 3} , and even when restricted to graphs with a given string representation consisting of straight line segments. 3-colorings of string graphs, when they exist, can be found in the subexponential time bound 2 O ( n 2 / 3 log n ) {\displaystyle 2^{O(n^{2/3}\log n)}} , but a similarly fast time for more colors is unlikely, under standard complexity-theoretic assumptions: an algorithm for 4-coloring in time 2 o ( n ) {\displaystyle 2^{o(n)}} would contradict the exponential time hypothesis.
… excerpt ends here. Continue reading the full article.
