کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6425985 | 1345399 | 2012 | 21 صفحه PDF | دانلود رایگان |
Given a collection C of curves in the plane, its string graph is defined as the graph with vertex set C, in which two curves in C are adjacent if and only if they intersect. Given a partially ordered set (P,<), its incomparability graph is the graph with vertex set P, in which two elements of P are adjacent if and only if they are incomparable.It is known that every incomparability graph is a string graph. For “dense” string graphs, we establish a partial converse of this statement. We prove that for every ε>0 there exists δ>0 with the property that if C is a collection of curves whose string graph has at least ε|C|2 edges, then one can select a subcurve γⲠof each γâC such that the string graph of the collection {γâ²:γâC} has at least δ|C|2 edges and is an incomparability graph. We also discuss applications of this result to extremal problems for string graphs and edge intersection patterns in topological graphs.
Journal: Advances in Mathematics - Volume 230, Issue 3, 20 June 2012, Pages 1381-1401