The maximal 1-planarity and crossing numbers of graphs (Q2042209)

This paper deals with 1-planar graphs and their crossing number. A 1-planar graph is a graph that has a drawing on the plane where each edge has at most one crossing. Hence, a 1-planar graph is a superfamily of planar graphs. It is known, due to a result by \textit{J. Czap} and \textit{D. Hudák} [Electron. J. Comb. 20, No. 2, Research Paper P54, 8 p. (2013; Zbl 1295.05084)], that the crossing number of a 1-planar graph on \(n\) vertices is at most \(n-2\). The first result of the paper is an improvement of this upper bound: the authors show that in fact a better upper bound is \[n-2-\frac{1}{6}(2\lambda_1+2\lambda_2+\lambda_3),\] where \(\lambda_1\) and \(\lambda_2\) are the number of vertices of degree 2 and 4 in \(G\), respectively, and \(\lambda_3\) is the more technical parameter counting the number of vertices of odd degree \(w\) in \(G\) such that either their degree is less or equal than 9 or \(G- w\) is 2-connected. The second main result of the paper gets an upper bound for maximal 1-planar graphs: the authors show that a maximal 1-planar 3-connected graph on \(n\) vertices and \(m\) edges has crossing number exactly \(m-3n + 6\).