Drawing Graph Joins in the Plane With Restrictions on Crossings

Ju´Lius Czapa, Peter Sˇugereka

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 $\frac35n-\frac65$ crossings. Consequently, every $n$-vertex 1-planar graph of class $\mathcal C_1$ has at most $\frac{18}5n-\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 $\frac35n-\frac65$ crossings. Next we present a construction of $n$-vertex 1-planar graphs of class $\mathcal C_1$ with $\frac{18}5n-\frac{36}5$ edges. Finally, we present the decomposition of 1-planar join products.