Simple Topological Drawings of k-Planar Graphs
share
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 f : ℕ→ℕ such that every k-planar graph admits an f(k)-plane simple drawing, for all k∈ℕ. 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.
READ FULL TEXT