Standard

On the rectilinear crossing number of complete uniform hypergraphs. / Anshu, Anurag; Gangopadhyay, Rahul; Shannigrahi, Saswata; Vusirikala, Satyanarayana.

In: Computational Geometry: Theory and Applications, Vol. 61, 01.02.2017, p. 38-47.

Research output: Contribution to journal › Article › peer-review

Harvard

Anshu, A, Gangopadhyay, R, Shannigrahi, S & Vusirikala, S 2017, 'On the rectilinear crossing number of complete uniform hypergraphs', Computational Geometry: Theory and Applications, vol. 61, pp. 38-47. https://doi.org/10.1016/j.comgeo.2016.11.001

APA

Anshu, A., Gangopadhyay, R., Shannigrahi, S., & Vusirikala, S. (2017). On the rectilinear crossing number of complete uniform hypergraphs. Computational Geometry: Theory and Applications, 61, 38-47. https://doi.org/10.1016/j.comgeo.2016.11.001

Vancouver

Anshu A, Gangopadhyay R, Shannigrahi S, Vusirikala S. On the rectilinear crossing number of complete uniform hypergraphs. Computational Geometry: Theory and Applications. 2017 Feb 1;61:38-47. https://doi.org/10.1016/j.comgeo.2016.11.001

Author

Anshu, Anurag ; Gangopadhyay, Rahul ; Shannigrahi, Saswata ; Vusirikala, Satyanarayana. / On the rectilinear crossing number of complete uniform hypergraphs. In: Computational Geometry: Theory and Applications. 2017 ; Vol. 61. pp. 38-47.

BibTeX

@article{112e7a86211d4037a6472c26b43490cc,
title = "On the rectilinear crossing number of complete uniform hypergraphs",
abstract = "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).",
keywords = "Crossing simplices, Gale Transform, Ham–Sandwich Theorem, Moment curve",
author = "Anurag Anshu and Rahul Gangopadhyay and Saswata Shannigrahi and Satyanarayana Vusirikala",
year = "2017",
month = feb,
day = "1",
doi = "10.1016/j.comgeo.2016.11.001",
language = "English",
volume = "61",
pages = "38--47",
journal = "Computational Geometry: Theory and Applications",
issn = "0925-7721",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - On the rectilinear crossing number of complete uniform hypergraphs

AU - Anshu, Anurag

AU - Gangopadhyay, Rahul

AU - Shannigrahi, Saswata

AU - Vusirikala, Satyanarayana

PY - 2017/2/1

Y1 - 2017/2/1

N2 - 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).

AB - 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).

KW - Crossing simplices

KW - Gale Transform

KW - Ham–Sandwich Theorem

KW - Moment curve

UR - http://www.scopus.com/inward/record.url?scp=84998827999&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2016.11.001

DO - 10.1016/j.comgeo.2016.11.001

M3 - Article

AN - SCOPUS:84998827999

VL - 61

SP - 38

EP - 47

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

SN - 0925-7721

ER -

ID: 49848890