Content deleted Content added
→Related graph classes: supply requested citation |
→Related graph classes: sinden is also the source of the subdivided K5 |
||
Line 7:
==Related graph classes==
[[File:Planar string graph.svg|thumb|300px|Representation of a [[planar graph]] as a string graph.]]
Every [[planar graph]] is a string graph:<ref name="ss-s">{{harvtxt|Schaefer|Štefankovič|2001}} credit this observation to {{harvtxt|Sinden|1966}}.</ref> 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. {{harvtxt|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.
[[File:Subdivided K5.svg|thumb|180px|A subdivision of ''K''<sub>5</sub> that is not a string graph.]]
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''<sub>5</sub> shown in the illustration is not a string graph, because ''K''<sub>5</sub> is not planar.<ref name="ss-s"/>
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.
| |||