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 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. 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 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.
Read more about this topic: String Graph
Famous quotes containing the words related, graph and/or classes:
“The custard is setting; meanwhile
I not only have my own history to worry about
But am forced to fret over insufficient details related to large
Unfinished concepts that can never bring themselves to the point
Of being, with or without my help, if any were forthcoming.”
—John Ashbery (b. 1927)
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)
“Is a man too strong and fierce for society, and by temper and position a bad citizen,—a morose ruffian, with a dash of the pirate in him;Mnature sends him a troop of pretty sons and daughters, who are getting along in the dame’s classes at the village school, and love and fear for them smooths his grim scowl to courtesy. Thus she contrives to intenerate the granite and the feldspar, takes the boar out and puts the lamb in, and keeps her balance true.”
—Ralph Waldo Emerson (1803–1882)