A graph is 1-planar if it can be drawn in the plane so that each edge is crossed at most once. However, there are 1-planar graphs which do not admit a straight-line 1-planar drawing. We show that every 1-planar graph has a straight-line drawing with a two-coloring of the edges, so that edges of the same color do not cross. Hence, 1-planar graphs have geometric thickness two. In addition, each edge is crossed by edges with a common vertex if it is crossed more than twice. The drawings use high precision arithmetic with numbers with O(n log n) digits and can be computed in linear time from a 1-planar drawing
翻译：如果能够在平面上绘制图形,使每个边缘最多经过一次,则图形为 1 平图为 1 平图。然而,有 1 平图不包含直线 1 平图。我们显示,每个 1 平图有一条直线图,带有两色的边缘,因此同一颜色的边缘不会交叉。因此, 1 平图有几何厚度 2 。此外,每个边缘如果跨过两次以上,则由带有共同顶层的边缘跨过。图纸使用O(nlog n)数字的高精度算术和O(nlog n)数字,可以用一平图的直线时间计算。
相关内容
微信扫码咨询专知VIP会员