String graph: Difference between revisions

Revision as of 23:52, 27 May 2025

Latest revision as of 11:59, 15 July 2025

(3 intermediate revisions by 3 users not shown)

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>

Line 57:

| title = Optimality program in segment and string graphs

| volume = 81

| year = 2019}}.| doi-access = free

}}.

*{{citation

| last1 = Chalopin | first1 = J. | last2 = Gonçalves | first2 = D. | last3 = Ochem | first3 = P.

Line 105 ⟶ 106:

| title = String graphs and incomparability graphs

| volume = 230

| year = 2012}}| hdl = 1721.1/98834

| hdl-access = free

}}.

*{{citation

| first1 = M. C. | last1 = Golumbic |author1-link = Martin Charles Golumbic | first2 = D. | last2 = Rotem | first3 = J. | last3 = Urrutia | author3-link = Jorge Urrutia Galicia

| title = Comparability graphs and intersection graphs

| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]