Simple Topological Drawings of k-Planar Graphs

Abstract

Every finite graph admits a simple (topological) drawing, that is, a drawing where every pair of edges intersects in at most one point. However, in combination with other restrictions simple drawings do not universally exist. For instance, k-planar graphs are those graphs that can be drawn so that every edge has at most k crossings (i.e., they admit a k-plane drawing). It is known that for k≤3 , every k-planar graph admits a k-plane simple drawing. But for k≥4 , there exist k-planar graphs that do not admit a k-plane simple drawing. Answering a question by Schaefer, we show that there exists a function Open image in new window such that every k-planar graph admits an f(k)-plane simple drawing, for all Open image in new window. Note that the function f depends on k only and is independent of the size of the graph. Furthermore, we develop an algorithm to show that every 4-planar graph admits an 8-plane simple drawing.