Crossings in grid drawings
We prove tight crossing number inequalities for geometric graphs whose vertex sets are taken from a d-dimensional grid of volume N and give applications of these inequalities to counting the number of crossing-free geometric graphs that can be drawn on such grids. In particular, we show that any geometric graph with m ≥ 8N edges and with vertices on a 3D integer grid of volume N, has Ω((m2/N) log(m/N)) crossings. In d-dimensions, with d ≥ 4, this bound becomes Ω(m2/N). We provide matching upper bounds for all d. Finally, for d ≥ 4 the upper bound implies that the maximum number of crossing-free geometric graphs with vertices on some d-dimensional grid of volume N is NΘ(N). In 3 dimensions it remains open to improve the trivial bounds, namely, the 2Ω(N) lower bound and the NO(N) upper bound.
|Keywords||Graph drawing, Grid drawing|
|Journal||Electronic Journal of Combinatorics|
Dujmović, V, Morin, P, & Sheffer, A. (Adam). (2014). Crossings in grid drawings. Electronic Journal of Combinatorics, 21(1).
|Publisher's version Final Version|