Crossings in grid drawings

Vida Dujmović¹ ; Pat Morin² ; Adam Sheffer³

¹School of Computer Science and Electrical Engineering University of Ottawa
²School of Computer Science, Carleton University
³School of Computer Science, Tel-Aviv University

The electronic journal of combinatorics, Tome 21 (2014) no. 1

Résumé

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\geq 8N$ edges and with vertices on a 3D integer grid of volume $N$, has $\Omega((m^2/N)\log(m/N))$ crossings. In $d$-dimensions, with $d\ge 4$, this bound becomes $\Omega(m^2/N)$. We provide matching upper bounds for all $d$. Finally, for $d\ge 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^{\Theta(N)}$. In 3 dimensions it remains open to improve the trivial bounds, namely, the $2^{\Omega(N)}$ lower bound and the $N^{O(N)}$ upper bound.

Détail

DOI : 10.37236/3025

Classification : 05C62, 05C10, 68U05
Mots-clés : graph drawing, grid drawing