The classes of \(k\) -planar, fan-crossing free,
fan-crossing, quasi-planar, \(k\) -gap-planar, and right-angle crossing
graphs are denoted by \(k\)PLANAR,
FCF, FAN,
QUASI, \(k\)GAP, and RAC, respectively. Then 0PLANAR\(=\)  0GAP is the class of
planar graphs.
These and other classes have been studied with different intensity
and depth. In particular, the density
[1]}, [2]}, which is the
maximal number of edges of \(n\) -vertex graphs, and the size of the
largest complete (bipartite) graph [3]} are
well explored, see Table REF  and Fig. REF .
It has been shown that the recognition problem is
NP-complete for 1-planar [4]}, [5]},
fan-crossing (fan-planar) [6]}, 1-gap-planar
[7]}, and RAC graphs [8]}, whereas a
proof for the NP-completeness is still missing for \(k\) -planar,
\(k\) -gap-planar, fan-crossing free, and quasi-planar graphs if \(k\ge 2\)  [1]}.
