The density of fan-planar graphs (Q2121760)

Summary: A topological drawing of a graph is fan-planar if for each edge \(e\) the edges crossing \(e\) form a star and no endpoint of \(e\) is enclosed by \(e\) and its crossing edges. A fan-planar graph is a graph admitting such a drawing. Equivalently, this can be formulated by three forbidden patterns, one of which is the configuration where \(e\) is crossed by two independent edges and the other two where \(e\) is crossed by two incident edges in a way that encloses some endpoint of \(e\). A topological drawing is simple if any two edges have at most one point in common. Fan-planar graphs are a new member in the ever-growing list of topological graphs defined by forbidden intersection patterns, such as planar graphs and their generalizations, Turán-graphs and Conway's thrackle conjecture. Hence fan-planar graphs fall into an important field in combinatorial geometry with applications in various areas of discrete mathematics. As every \(1\)-planar graph is fan-planar and every fan-planar graph is \(3\)-quasiplanar, they also fit perfectly in a recent series of works on nearly-planar graphs from the areas of graph drawing and combinatorial embeddings. In this paper we show that every fan-planar graph on \(n\) vertices has at most \(5n-10\) edges, even though a fan-planar drawing may have a quadratic number of crossings. Our bound, which is tight for every \(n \geq 20\), indicates how nicely fan-planar graphs fit in the row with planar graphs \((3n-6\) edges) and \(1\)-planar graphs \((4n-8\) edges). With this, fan-planar graphs form an inclusion-wise largest non-trivial class of topological graphs defined by forbidden patterns, for which the maximum number of edges on \(n\) vertices is known exactly. We demonstrate that maximum fan-planar graphs carry a rich structure, which makes this class attractive for many algorithms commonly used in graph drawing. Finally, we discuss possible extensions and generalizations of these new concepts.