On the Density of 3-Planar Graphs
Michael A. Bekos, Michael Kaufmann, Chrysanthi N. Raftopoulou · arXiv (Cornell University) · 2016
A $k$-planar graph is one that can be drawn in the plane such that every edge is crossed at most $k$ times. For $k \leq 4$, Path and T\'oth proved a bound of $(k+3)(n-2)$ on the total number of edges of a $k$-planar graph, which is tight for $k=1,2$. For $k=3$, we improve their bound from $6n-12$ to $\frac{11}{2}n-11$ and we also show that this is tight for multi-graphs with no homotopic edges.