Fan-crossing free graphs and their relationship to other beyond-planar graphs (Q2663047)

Beyond-planar graphs are those graphs that have drawings with specific restrictions on crossings. Some classes discussed in the paper are briefly defined next. A fan is a set of edges with a common vertex. There is a fan-crossing in a drawing of a graph if an edge is crossed by the edges of a fan. An edge is uncrossed if it has a fan-crossing by a fan of size zero. A graph is \(k\)-planar if it has a drawing in the plane so that each edge is crossed by at most \(k\) edges. It is fan-crossing-free if the crossing edges are independent (i.e., form a matching), and fan-crossing if the crossing edges form a fan. A drawing of a graph is \(k\)-quasi-planar if \(k\) edges do not mutually cross. When \(k=3\), these are quasi-planar. A drawing is \(k\)-gap-planar if every crossing is assigned to an edge involved in the crossing so that each edge has at most \(k\) crossings assigned to it. Right-angle crossing (RAC) asks for a straight-line drawing in which crossings are at a right angle. This paper explores relationships among these and other classes, focussing on the use of three operations (subdivision, node-to-circle expansion and path-addition) to distinguish them. It also establishes that the recognition of fan-crossing-free graphs is NP-complete.