String graph
Encyclopedia
In graph theory
, a string graph is an intersection graph
of curve
s 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, drawn in the plane such that no three strings intersect at a single point and such that the graph having a vertex for each curve and an edge for each intersecting pair of curves is isomorphic to G.
s. Later, specified the same idea to electrical networks and printed circuits. The mathematical study of string graphs began with the paper 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.
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 uv of the graph, the strings for u and v cross each other twice near the midpoint of 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. 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 is subdivided, the resulting graph is a string graph if and only if G is planar. In particular, the subdivision of the complete graph
K5 shown in the illustration is not a string graph, because K5 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
is also a string graph.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a string graph is an intersection graph
Intersection graph
In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...
of curve
Curve
In mathematics, a curve is, generally speaking, an object similar to a line but which is not required to be straight...
s 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, drawn in the plane such that no three strings intersect at a single point and such that the graph having a vertex for each curve and an edge for each intersecting pair of curves is isomorphic to G.
Background
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 graphInterval graph
In graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.-Definition:...
s. Later, specified the same idea to electrical networks and printed circuits. The mathematical study of string graphs began with the paper and
through a collaboration between Sinden and Ronald Graham
Ronald Graham
Ronald Lewis Graham is a mathematician credited by the American Mathematical Society as being "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years"...
, 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
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
, implying that no simple characterization is likely to exist.
Related graph classes
Every planar graphPlanar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
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 uv of the graph, the strings for u and v cross each other twice near the midpoint of 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
Circle packing theorem
The circle packing theorem describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles whose interiors are disjoint...
, 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. 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
Scheinerman's conjecture
In mathematics, Scheinerman's conjecture, now a theorem, states that every planar graph is the intersection graph of a set of line segments in the plane. This conjecture was formulated by E. R. Scheinerman in his Ph.D. thesis , following earlier results that every planar graph could be represented...
, 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 is subdivided, the resulting graph is a string graph if and only if G is planar. In particular, the subdivision of the complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
K5 shown in the illustration is not a string graph, because K5 is not planar.
Every circle graph
Circle graph
In graph theory, a circle graph is the intersection graph of a set of chords of a circle. That is, it is an undirected graph whose vertices can be associated with chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other.-Algorithmic...
, as an intersection graph of line segments (the chords of a circle), is also a string graph. Every chordal graph
Chordal graph
In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...
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
Complement graph
In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...
of every comparability graph
Comparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...
is also a string graph.