Simple Topological Drawings of k-Planar Graphs
Journal
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Journal Volume
12590 LNCS
Pages
390-402
Date Issued
2020
Author(s)
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 such that every k-planar graph admits an f(k)-plane simple drawing, for all. 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. © 2020, Springer Nature Switzerland AG.
Subjects
k-planar graphs; Local crossing number; Topological graphs
Other Subjects
Drawing (graphics); Graph theory; Visualization; Finite graphs; Planar graph; Graph algorithms
Type
conference paper