String Graph on:
[Wikipedia]
[Google]
[Amazon]
In
Every planar graph is a string graph: credit this observation to . 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 Subdivision (graph theory), subdivided, the resulting graph is a string graph if and only if ''G'' is planar. In particular, the subdivision of the complete graph ''K''5 shown in the illustration is not a string graph, because ''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 is also a string graph.
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, a string graph is an intersection graph
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...
of curves in the plane; each curve is called a "string". Given a graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
, is a string graph if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicondi ...
there exists a set of curves, or strings, such that the graph having a vertex
Vertex, vertices or vertexes may refer to:
Science and technology Mathematics and computer science
*Vertex (geometry), a point where two or more curves, lines, or edges meet
*Vertex (computer graphics), a data structure that describes the position ...
for each curve and an edge for each intersecting pair of curves is isomorphic
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
to .
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 ofinterval graph
In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line,
with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals.
Int ...
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 Lewis Graham (October 31, 1935July 6, 2020) was an American mathematician credited by the American Mathematical Society as "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years". He ...
, 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
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
, implying that no simple characterization is likely to exist.
Related graph classes
Every planar graph is a string graph: credit this observation to . 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 Subdivision (graph theory), subdivided, the resulting graph is a string graph if and only if ''G'' is planar. In particular, the subdivision of the complete graph ''K''5 shown in the illustration is not a string graph, because ''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 is also a string graph.
Other results
showed computing the chromatic number of string graphs to be NP-hard. found that string graphs form an induced minor closed class, but not a minor closed class of graphs. Every ''m''-edge string graph can be partitioned into two subsets, each a constant fraction the size of the whole graph, by the removal of ''O''(''m''3/4log1/2''m'') vertices. It follows that the Biclique-free graph, biclique-free string graphs, string graphs containing no ''K''''t'',''t'' subgraph for some constant ''t'', have ''O''(''n'') edges and more strongly have bounded expansion, polynomial expansion.; .Notes
References
*. *. *. *. *. *. *. *. *. *. *. *. *. *{{citation , journal = Bell System Technical Journal , title = Topology of thin film RC-circuits , first = F. W. , last = Sinden , year = 1966 , volume = 45 , issue = 9 , pages = 1639–1662 , doi=10.1002/j.1538-7305.1966.tb01713.x. Topological graph theory Intersection classes of graphs