Fan-Planar Graphs

A fan-planar graph is a graph that admits a drawing, in which each edge can cross only edges with a common endvertex, and this endvertex is on the same side of the edge. Hence, by definition, fan-planar graphs extend the class of 1-planar graphs, but still form a proper subclass of 3-quasiplanar graphs, as they cannot contain three mutually crossing edges. Similarly to several other classes of beyond-planar graphs, fan-planar graphs have a linear number of edges, it is NP-hard to recognize them (both in general and in the fixed rotation system setting), while polynomial-time recognition and drawing algorithms are known only for special variants of them. In this chapter, we review known combinatorial and algorithmic results on fan-planar graphs and we identify several open problems in the field.