Saturated 2-plane drawings with few edges

Abstract

A drawing of a graph is k-plane if every edge contains at most k crossings. A k-plane drawing is saturated if we cannot add any edge so that the drawing remains k-plane. It is well-known that saturated 0-plane drawings, that is, maximal plane graphs, of n vertices have exactly 3n − 6 edges. For k > 0, the number of edges of saturated n-vertex k-plane graphs can take many different values. In this note, we establish some bounds on the minimum number of edges of saturated 2-plane graphs under various conditions.