On fan-crossing graphs (Q2202017)

This paper explores drawings of graphs in which the types of edge crossings are restricted. A fan is a set of edges that are all incident with a common vertex. A plane drawing of a graph is fan-crossing if, for each edge, the edges that cross it form a fan. If one further requires that all crossing edges have the common vertex of the fan on the same side of the crossed edge, the drawing is fan-planar. Provided that every two edges that cross a single edge share a vertex, a drawing is adjacency-crossing. One extends the definitions from drawings to graphs, so that a graph is fan-crossing, fan-planar, or adjacency-crossing if it admits a plane drawing of the type indicated. This paper establishes that every adjacency-crossing graph is fan-crossing. It is further shown that not all fan-crossing graphs are fan-planar, but whenever an \(n\)-vertex \(m\)-edge fan-crossing graph exists, so does an \(n\)-vertex \(m\)-edge fan-planar graph. Moreover, \(n\)-vertex fan-crossing and fan-planar graphs each contain at most \(5n-10\) edges.