Three classes of 1-planar graphs

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 this paper we decompose the set of all 1-planar graphs into three classes ${\mathcal{C}}_0,{\mathcal{C}}_1$ and ${\mathcal{C}}_2$ with respect to the types of crossings and present the decomposition of 1-planar join products. Zhang \cite{z} proved that every $n$-vertex 1-planar graph of class ${\mathcal{C}}_1$ has at most $\frac{18}{5}n-\frac{36}{5}$ edges and a ${\mathcal{C}}_1$-drawing with at most $\frac{3}{5}n-\frac{6}{5}$ crossings. We improve these results. We show that every ${\mathcal{C}}_1$-drawing of a 1-planar graph has at most $\frac{3}{5}n-\frac{6}{5}$ crossings. Consequently, every $n$-vertex 1-planar graph of class ${\mathcal{C}}_1$ has at most $\frac{18}{5}n-\frac{36}{5}$ edges. Moreover, we prove that this bound is sharp.

Cited by in corpus (2)

• An annotated bibliography on 1-planarity
• A Survey on Graph Drawing Beyond Planarity