On the Relationship Between k-Planar and k-Quasi-Planar Graphs

A 3-planar simple topological graph with a tangled 4-crossing


A simple topological graph is $k$-quasiplanar ($k\geq 2$) if it contains no $k$ pairwise crossing edges, and $k$-planar if no edge is crossed more than k times. In this paper, we explore the relationship between $k$-planarity and $k$-quasiplanarity to show that, for $k\geq 2$, every $k$-planar simple topological graph can be transformed into a $(k+1)$-quasiplanar simple topological graph.

In 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017)