Fan-Planar Graphs: Combinatorial Properties and Complexity Results - Graph Drawing - page 186

(a) (b)

Fig. 1. (a) A fan-planar drawing of a graph G with 12 crossings; (b) A confluent drawing of G
with 3 crossings

number of edges that a drawing of type T can have; this problem is usually dubbed
aTuran-type problem, and several tight bounds have been proved for the types
of drawings mentioned above, both for straight-line and for polyline edges (see,
e.g., [1,2,4,10,11,18,19,21,24,30,33]). From the algorithmic point of view, the com-
plexity of testing whether a graph G admits a drawing of type T is one of the most
interesting. Also for this problem several results have been shown, both in the variable
and in the fixed embedding setting (see, e.g., [8,12,13,25,26,29]).
In this paper we investigate fan-planardrawings of graphs, in which an edge can-
not cross two independent edges, i.e., an edge can cross several edges provided that
they have a common end-vertex. Fan-planar drawings have been recently introduced
by Kaufmann and Ueckerdt [28]; they proved that every n -vertex graph without loops
and multiple edges that admits a fan-planar drawing has at most 5 n − 10 edges, and

that this bound is tight for n 20. Fan-planar drawings are on the opposite side of

fan-crossing free drawings mentioned above. Besides its intrinsic theoretical interest,
we observe that fan-planarity can be also used for creating drawings with few edge
crossings in a confluent drawing style (see, e.g., [17,23]). For example, Fig.1(a)shows
a fan-planar drawing ʓ with 12 crossings; Fig. 1(b) shows a new drawing with just 3
crossings obtained from ʓ by bundling crossing “fans”.
We prove both combinatorial properties and complexity results related to fan-planar
drawingsofgraphs. The main contributions of our work are as follows:
( i ) We s tudy the density of constrained versions of fan-planar drawings (Sec. 3), namely
outer fan-planardrawings , where all vertices must lie on the external boundary of the
drawing,and2 -layer fan-planardrawings , where vertices are placed on two distinct
horizontal lines and edges are vertically monotone lines. We prove tight bounds for
the edge density of these drawings. Namely, we show that n -vertex outer fan-planar
drawingshaveatmost3 n

≥

− 5 edges (a tight bound for n ≥ 5), and that n -vertex 2-

layer fan-planar drawingshaveatmost2 n 3). We

remark that outer and 2-layer non-planar drawings have been previously studied in the
1-planarity setting [8,18,26] and in the RAC planarity setting [12,13].
( ii ) Since general fan-planar drawable graphs have at most 5 n

− 4 edges (a tight bound for n ≥

10 edges and the same
bound holds for 2-planar drawable graphs [30], we investigate the relationship between
these two graph classes. More in general, we are able to prove that in fact for any k

−

≥ 2

there exist fan-planar drawable graphs that are not k -planar, and vice versa (Sec. 4).