String graph: Difference between revisions

Revision as of 13:45, 25 April 2017

Revision as of 15:32, 24 July 2017

Line 15:

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.<ref>{{harvtxt|Golumbic|Rotem|Urrutia|1983}} and {{harvtxt|Lovász|1983}}. See also {{harvtxt|Fox|Pach|20092010}}.</ref>

==Other results==

{{harvtxt|Ehrlich|Even|Tarjan|1976}} showed computing the chromatic number of string graphs to be NP-hard. {{harvtxt|Kratochvil|1991a}} found that string graphs form an induced minor closed class, but not a minor closed class of graphs.

Every ''m''-edge string graph can be partitioned into two subsets, each a constant fraction the size of the whole graph, by the removal of ''O''(''m''^3/4log^1/2''m'') edges. It follows that the [[Biclique-free graph|biclique-free string graphs]], string graphs containing no ''K''_''t'',''t'' subgraph for some constant ''t'', have ''O''(''n'') edges and more strongly have [[bounded expansion|polynomial expansion]].<ref>{{harvtxt|Fox|Pach|20092010}}; {{harvtxt|Dvořák|Norin|2015}}.</ref>

==Notes==

Line 69:

| title = A separator theorem for string graphs and its applications

| volume = 19

| year = 20092010}}.

*{{citation

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