Simple Topological Drawings of k-Planar Graphs

DOI10.1007/978-3-030-68766-3_31arXiv2008.10794MaRDI QIDQ6347671FDOQ6347671

Authors: Chih-Hung Liu, Meghana M. Reddy, Csaba D. Tóth 

Publication date: 24 August 2020

Abstract: Every finite graph admits a emph{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, emph{$k$-planar graphs} are those graphs that can be drawn so that every edge has at most $k$ crossings (i.e., they admit a emph{$k$-plane drawing}). It is known that for $kle3$, every $k$-planar graph admits a $k$-plane simple drawing. But for $kge4$, 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:mathbbNightarrowmathbbN$ such that every $k$-planar graph admits an $f(k)$-plane simple drawing, for all $kinmathbbN$. 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.

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

This page was built for publication: Simple Topological Drawings of $k$-Planar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6347671)