Cubic Planar Graphs that cannot be Drawn on few Lines
Cubic Planar Graphs that cannot be Drawn on few Lines
复制标题
无法用几条线绘制的立方平面图
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
D. Eppstein
中科院分区：
文献类型：
--
作者：
D. Eppstein
对于每一个整数$ell$，我们构造了一个具有$O(ell^3)$顶点的三次3顶点连通平面二部图$G$，使得$G$没有顶点都位于$ell$直线上的平面直线图$G$。这加强了以前在不能在几条线上绘制的图上的结果，这些图构建了更大的最大平面图。我们还发现顶点树和三次二部级数并行图不能在有限的直线上绘制。
For every integer $ell$, we construct a cubic 3-vertex-connected planar bipartite graph $G$ with $O(ell^3)$ vertices such that there is no planar straight-line drawing of $G$ whose vertices all lie on $ell$ lines. This strengthens previous results on graphs that cannot be drawn on few lines, which constructed significantly larger maximal planar graphs. We also find apex-trees and cubic bipartite series-parallel graphs that cannot be drawn on a bounded number of lines.