Drawing Graph Joins in the Plane with Restrictions on Crossings

Abstract

A graph is called 1-planar if it can be drawn in the plane so that each of its edges is crossed by at most one other edge. In 2014, Zhang showed that the set of all 1-planar graphs can be decomposed into three classes $\mathcal C_0, \mathcal C_1$ and $\mathcal C_2$ with respect to the types of crossings. He proved that every $n$-vertex 1-planar graph of class $\mathcal C_1$ has a $\mathcal C_1$-drawing with at most $\frac 35 n-\frac 65$ crossings. Consequently, every $n$-vertex 1-planar graph of class $\mathcal C_1$ has at most $\frac{18}{5}n-\frac{36}{5}$ edges.

In this paper we prove a stronger result. We show that every $\mathcal C_1$-drawing of a 1-planar graph has at most $\frac 35 n-\frac 65$ crossings. Next we present a construction of $n$-vertex 1-planar graphs of class $\mathcal C_1$ with $\frac{18}{5}n-\frac{36}{5}$ edges. Finally, we present the decomposition of 1-planar join products.