K-planar graphs


There is a natural generalisation of planar graphs namely k-planar graphs. A graph is k-planar if it has a drawing in the plane in which each edge is involved in at most k crossings. The study of 1-planar graphs goes back to more than fifty years ago. More precisely 1-planar graphs have been introduced by Ringel. They have several applications in the areas of graph theory, graph algorithms, graph drawing, and computational geometry, see recent bibliography on 1-planar graphs and the 140 references therein [1]. For instance the complete graph K_6 is 1-planar or the following graph.

A 1-planar graph G with n vertices has at most 4n − 8 edges. More precisely we have the following theorem.

Theorem: Let G be a 1-planar graph with n vertices. Then the maximum number of edges of G is given by