Crossing Number of Simple 3-Plane Drawings

Abstract

We study 3-plane drawings, that is, drawings of graphs in which every edge has at most three crossings. We show how the recently developed Density Formula for topological drawings of graphs [9] can be used to count the crossings in terms of the number n of vertices. As a main result, we show that every 3-plane drawing has at most 5.5(n − 2) crossings, which is tight. In particular, it follows that every 3-planar graph on n vertices has crossing number at most 5.5n, which improves upon a recent bound [3] of 6.6n. To apply the Density Formula, we carefully analyze the interplay between certain configurations of cells in a 3-plane drawing. As a by-product, we also obtain an alternative proof for the known statement that every 3-planar graph has at most 5.5(n − 2) edges.