کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949156 1439985 2017 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the rectilinear crossing number of complete uniform hypergraphs
ترجمه فارسی عنوان
در شماره گذار مستطیلی از کلیدهای یکپارچه
کلمات کلیدی
عبور از ساده، قهوه سحر قهوه، تبدیل گیل، منحنی لحظه،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, , , ,