String graph: Difference between revisions

Revision as of 20:53, 25 October 2009

Revision as of 21:49, 25 October 2009

Line 5:

==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; [[Scheinerman's conjecture]], now proven, states that every planar graph may be represented by the intersection graph of straight line segments, which are a very special case of strings, and {{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. Every [[circle graph]], as an intersection graph of line segments, 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.<ref>{{harvtxt|Golumbic|Rotem|Urrutia|1983}} and {{harvtxt|Lovász|1983}}. See also {{harvtxt|Fox|Pach|2009}}.</ref>

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. {{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 representation 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.

Every [[planarcircle graph]] is a string graph; [[Scheinerman's conjecture]], nowas proven, states that every planar graph may be represented by thean intersection graph of straight line segments, which(the are a very special casechords of strings, and {{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. Every [[circle graph]], as an intersection graph of line segments), 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.<ref>{{harvtxt|Golumbic|Rotem|Urrutia|1983}} and {{harvtxt|Lovász|1983}}. See also {{harvtxt|Fox|Pach|2009}}.</ref>

The [[complement graph]] of every [[comparability graph]] is also a string graph.<ref>{{harvtxt|Golumbic|Rotem|Urrutia|1983}} and {{harvtxt|Lovász|1983}}. See also {{harvtxt|Fox|Pach|2009}}.</ref>

==Other results==