论文标题
图表的平面图
Planar projections of graphs
论文作者
论文摘要
我们介绍并研究了一个新的图表表示，其中顶点嵌入了三个或多个维度，并将边缘在轴平行平面上绘制。我们表明，$ n $ Vertices上的完整图在$ \ lceil \ sqrt {n/2} +1 \ rceil $ planes中具有表示形式。在3个维度中，我们表明存在具有$ 6n-15 $边缘的图形，可以投影到两个正交平面上，这是最好的。最后，我们从几何厚度和线性支撑性等参数方面获得边界。使用这样的界限，我们表明，最大程度5的每个图都具有3个维度的平面预测表示。
We introduce and study a new graph representation where vertices are embedded in three or more dimensions, and in which the edges are drawn on the projections onto the axis-parallel planes. We show that the complete graph on $n$ vertices has a representation in $\lceil \sqrt{n/2}+1 \rceil$ planes. In 3 dimensions, we show that there exist graphs with $6n-15$ edges that can be projected onto two orthogonal planes, and that this is best possible. Finally, we obtain bounds in terms of parameters such as geometric thickness and linear arboricity. Using such a bound, we show that every graph of maximum degree 5 has a plane-projectable representation in 3 dimensions.
