کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949156 | 1439985 | 2017 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the rectilinear crossing number of complete uniform hypergraphs
ترجمه فارسی عنوان
در شماره گذار مستطیلی از کلیدهای یکپارچه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
عبور از ساده، قهوه سحر قهوه، تبدیل گیل، منحنی لحظه،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper, we consider a generalized version of the rectilinear crossing number problem of drawing complete graphs on a plane. The minimum number of crossing pairs of hyperedges among all d-dimensional rectilinear drawings of a d-uniform hypergraph is known as the d-dimensional rectilinear crossing number of the hypergraph. The currently best-known lower bound on the d-dimensional rectilinear crossing number of a complete d-uniform hypergraph with n vertices in general position in Rd is Ω(2ddlogâ¡d)(n2d). In this paper, we improve this lower bound to Ω(2d)(n2d). We also consider the special case when all the vertices of a d-uniform hypergraph are placed on the d-dimensional moment curve. For such d-dimensional rectilinear drawings of the complete d-uniform hypergraph with n vertices, we show that the number of crossing pairs of hyperedges is Î(4dd)(n2d).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 61, February 2017, Pages 38-47
Journal: Computational Geometry - Volume 61, February 2017, Pages 38-47
نویسندگان
Anurag Anshu, Rahul Gangopadhyay, Saswata Shannigrahi, Satyanarayana Vusirikala,