Research output: Contribution to journal › Article › peer-review
In this paper, we study the d-dimensional rectilinear drawings of the complete d-uniform hypergraph K2d d. Anshu et al. (2017) [3] used Gale transform and Ham-Sandwich theorem to prove that there exist Ω(2d) crossing pairs of hyperedges in such a drawing of K2d d. We improve this lower bound by showing that there exist Ω(2dd) crossing pairs of hyperedges in a d-dimensional rectilinear drawing of K2d d. We also prove the following results. 1. There are Ω(2dd3/2) crossing pairs of hyperedges in a d-dimensional rectilinear drawing of K2d d when its 2d vertices are either not in convex position in Rd or form the vertices of a d-dimensional convex polytope that is t-neighborly but not (t+1)-neighborly for some constant t≥1 independent of d. 2. There are Ω(2dd5/2) crossing pairs of hyperedges in a d-dimensional rectilinear drawing of K2d d when its 2d vertices form the vertices of a d-dimensional convex polytope that is (⌊d/2⌋−t′)-neighborly for some constant t′≥0 independent of d.
Original language | English |
---|---|
Article number | 101578 |
Number of pages | 7 |
Journal | Computational Geometry: Theory and Applications |
Volume | 86 |
Early online date | 14 Oct 2019 |
DOIs | |
State | Published - Jan 2020 |
ID: 49848807