Content deleted Content added
→Related graph classes: +footnote |
|||
Line 15:
If every edge of a given graph <math>G</math> is [[Subdivision (graph theory)|subdivided]], the resulting graph is a string graph if and only if <math>G</math> is planar. In particular, the subdivision of the [[complete graph]] <math>K_5</math> shown in the illustration is not a string graph, because <math>K_5</math> 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.{{sfnp|Kratochvíl|1991a|pp=56–57}}
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|2010}} and {{harvtxt|Fox|Pach|2012}}.</ref>
| |||