论文标题
$ k $ - 平面图的简单拓扑图
Simple Topological Drawings of $k$-Planar Graphs
论文作者
论文摘要
每个有限图都允许一个\ emph {simple（拓扑）绘图}，即，每对边最多都相交的图形。但是，结合其他限制，简单图纸并不普遍。例如，\ emph {$ k $ -planar图}是可以绘制的图形，以便每个边缘最多都有$ k $ crossings（即，他们接纳\ emph {$ k $ - plane drawd}）。众所周知，对于$ k \ le 3 $，每个$ k $ - planar Graph都能承认$ k $ - 平面简单的图纸。但是对于$ k \ ge 4 $，存在不承认$ k $ - 平面简单绘图的$ k $ - 平面图。在回答Schaefer的问题时，我们表明存在一个函数$ f：\ mathbb {n} \ rightArrow \ Mathbb {n} $，因此每个$ k $ - planar图都可以允许所有$ k \ in \ kathbb {n} $。请注意，功能$ f $仅取决于$ k $，并且独立于图形的大小。此外，我们开发了一种算法，以表明每$ 4 $ - 平面图都可以容纳$ 8 $ - 平面简单的图纸。
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 $k\le 3$, every $k$-planar graph admits a $k$-plane simple drawing. But for $k\ge 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 : \mathbb{N}\rightarrow\mathbb{N}$ such that every $k$-planar graph admits an $f(k)$-plane simple drawing, for all $k\in\mathbb{N}$. 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.
