کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6868457 | 1439978 | 2018 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Note on k-planar crossing numbers
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The crossing numberCR(G) of a graph G=(V,E) is the smallest number of edge crossings over all drawings of G in the plane. For any kâ¥1, the k-planar crossing number of G, CRk(G), is defined as the minimum of CR(G0)+CR(G1)+â¦+CR(Gkâ1) over all graphs G0,G1,â¦,Gkâ1 with âªi=0kâ1Gi=G. It is shown that for every kâ¥1, we have CRk(G)â¤(2k2â1k3)CR(G). This bound does not remain true if we replace the constant 2k2â1k3 by any number smaller than 1k2. Some of the results extend to the rectilinear variants of the k-planar crossing number.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 68, March 2018, Pages 2-6
Journal: Computational Geometry - Volume 68, March 2018, Pages 2-6
نویسندگان
János Pach, László A. Székely, Csaba D. Tóth, Géza Tóth,