کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6423909 1632593 2011 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On disjoint crossing families in geometric graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On disjoint crossing families in geometric graphs
چکیده انگلیسی

A geometric graph is a graph drawn in the plane with vertices represented by points and edges as straight-line segments. A geometric graph contains a (k, l)-crossing family if there is a pair of edge subsets E1, E2 such that |E1|=k and |E2|=l, the edges in E1 are pairwise crossing, the edges in E2 are pairwise crossing, and every edges in E1 is disjoint to every edge in E2. We conjecture that for any fixed k, l, every n-vertex geometric graph with no (k,l)-crossing family has at most ck,ln edges, where ck,l is a constant that depends only on k and l. In this note, we show that every n-vertex geometric graph with no (k,k)-crossing family has at most cknlogn edges, where ck is a constant that depends only on k, by proving a more general result which relates extremal function of a geometric graph F with extremal function of two completely disjoint copies of F. We also settle the conjecture for geometric graphs with no (2, 1)-crossing family. As a direct application, this implies that for any circle graph F on 3 vertices, every n-vertex geometric graph that does not contain a matching whose intersection graph is F has at most O(n) edges.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 38, 1 December 2011, Pages 367-375
نویسندگان
, ,