×

On the rectilinear crossing number of complete uniform hypergraphs. (English) Zbl 1368.05106

Summary: 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 \(\mathbb{R}^d\) is \(\Omega({2^d\over\sqrt{d}}\log d){n\choose 2d}\).
In this paper, we improve this lower bound to \(\Omega(2^d){n\choose 2d}\). 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 a \(\Theta({4^d\over\sqrt{d}}){n\choose 2d}\).

MSC:

05C65 Hypergraphs
05C62 Graph representations (geometric and intersection representations, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ábrego, B. M.; Cetina, M.; Fernández-Merchant, S.; Leaños, J.; Salazar, G., On \((\leq k)\)-edges, crossings, and halving lines of geometric drawings of \(K_n\), Discrete Comput. Geom., 48, 192-215 (2012) · Zbl 1247.52010
[2] Anshu, A.; Shannigrahi, S., A lower bound on the crossing number of uniform hypergraphs, Discrete Appl. Math., 209, 11-15 (2016) · Zbl 1339.05267
[3] Breen, M., Primitive Radon partitions for cyclic polytopes, Isr. J. Math., 15, 156-157 (1973) · Zbl 0266.52004
[4] Dey, T. K.; Pach, J., Extremal Problems for Geometric Hypergraphs, (Proc. ISAAC 1996. Proc. ISAAC 1996, Lect. Notes Comput. Sci., vol. 1178 (1996)). (Proc. ISAAC 1996. Proc. ISAAC 1996, Lect. Notes Comput. Sci., vol. 1178 (1996)), Discrete Comput. Geom., 19, 473-484 (1998), also in: · Zbl 0902.05054
[5] Fabila-Monroy, R.; López, J., Computational search of small point sets with small rectilinear crossing number, J. Graph Algorithms Appl., 18, 3, 393-399 (2014) · Zbl 1295.05162
[6] Güler, O., Foundations of Optimization (2010), Springer Science and Business Media · Zbl 1220.90001
[7] He, X.; Kao, M. Y., Regular edge labelings and drawings of planar graphs, (Graph Drawing (1995)), 96-103
[8] Kainen, P. C., The book thickness of a graph II, Congr. Numer., 71, 121-132 (1990) · Zbl 0749.05030
[9] Matoušek, J., Lectures in Discrete Geometry (2002), Springer · Zbl 0999.52006
[10] McMullen, P., The maximum numbers of faces of a convex polytope, Mathematika, 17, 179-184 (1970) · Zbl 0217.46703
[11] Schaefer, M., The graph crossing number and its variants: a survey, Dynamic Survey. Dynamic Survey, Electron. J. Comb., 21 (2014) · Zbl 1267.05180
[12] Shahrokhi, F.; Sykora, O.; Szekely, L.; Vrto, I., The gap between the crossing numbers and the convex crossing numbers, Contemp. Math., 342, 249-258 (2004) · Zbl 1062.05050
[13] Tollis, I. G.; Xia, C., Drawing telecommunication networks, (Graph Drawing (1995)), 206-217
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.