Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
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 Ω(2ddlogd)(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).
Язык оригинала | английский |
---|---|
Страницы (с-по) | 38-47 |
Число страниц | 10 |
Журнал | Computational Geometry: Theory and Applications |
Том | 61 |
DOI | |
Состояние | Опубликовано - 1 фев 2017 |
ID: 49848890