Simplifying Non-Simple Fan-Planar Drawings

Abstract

A drawing of a graph is fan-planar if the edges intersecting a common edge a share a vertex A on the same side of a. More precisely, orienting a arbitrarily and the other edges towards A results in a consistent orientation of the crossings. So far, fan-planar drawings have only been considered in the context of simple drawings, where any two edges share at most one point, including endpoints. We show that every non-simple fan-planar drawing can be redrawn as a simple fan-planar drawing of the same graph while not introducing additional crossings. The proof is constructive and corresponds to a quadratic time algorithm. Combined with previous results on fan-planar drawings, this yields that n-vertex graphs having such a drawing can have at most 6.5n - 20 edges and that the recognition of such graphs is NP-hard. We thereby answer an open problem posed by Kaufmann and Ueckerdt in 2014.