2016 | OriginalPaper | Chapter
On the Density of Non-simple 3-Planar Graphs
Authors: Michael A. Bekos, Michael Kaufmann, Chrysanthi N. Raftopoulou
Publisher: Springer International Publishing
Published in:
Graph Drawing and Network Visualization
Abstract
A k-planar graph is a graph that can be drawn in the plane such that every edge is crossed at most k times. For \(k \le 4\), Pach and Tóth [20] 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\), the bound of \(6n-12\) has been improved to \(\frac{11}{2}n-11\) in [19] and has been shown to be optimal up to an additive constant for simple graphs. In this paper, we prove that the bound of \(\frac{11}{2}n-11\) edges also holds for non-simple 3-planar graphs that admit drawings in which non-homotopic parallel edges and self-loops are allowed. Based on this result, a characterization of optimal 3-planar graphs (that is, 3-planar graphs with n vertices and exactly \(\frac{11}{2}n-11\) edges) might be possible, as to the best of our knowledge the densest known simple 3-planar is not known to be optimal.
