主题
Search

几乎平面图


文献中使用了几种不同的几乎平面(以及近乎平面)的定义(参见 Lipton et al. 2016)。

例如,Gubser (1996) 将几乎平面图 G 定义为满足 G-eG\e 之一是平面图的图,其中 G-e 表示边删除,G\E 表示边收缩。

根据 Karpov (2013) 的定义,称 k-平面图为可以在平面上绘制的图,使得任何边最多与其他 k 条边相交 (Pach and Tóth 1997, Karpov 2013)。那么 0-平面图对应于 平面图,而 1-平面图可以称为几乎平面图 (Karpov 2013),本文采用此约定。

beta(n)n>=4 个顶点上的 二部 几乎平面图的最大边数,则

 beta(n)={3n-8   for even n!=6; 3n-9   for odd n or n=6
(1)

(Karpov 2013)。由此可见,任何 1-平面 二部图 的最小度数最多为 5,其顶点数至少为 16。 16 个顶点上的 41 个五次二部图似乎都不是 1-平面的,截至 2022 年 9 月,已知的最小 五次 二部 1-平面图的顶点数为 32 个(如下所示;LeechLattice 2022)。

AlmostPlanarBipartiteGraphs

唯一的几乎平面的 完全二部图K_(1,n)K_(2,n)K_(3,3)K_(3,4)K_(3,5)K_(3,6)K_(4,4) (Karpov 2013)。


另请参阅

图交叉数, 平面图, 单交叉图

使用 探索

参考文献

Gubser, B. S. "A Characterization of Almost-Planar Graphs." Combin. Prob. Comput. 5, 227-245, 1996.Karpov, D. V. "Upper Bound on the Number of Edges of an Almost Planar Bipartite Graph." 3 Jul 2013. https://arxiv.org/abs/1307.1013.LeechLattice. "How to Construct a 5-Regular 1-Planar Bipartite Graph?" Sep. 10, 2022. https://mathoverflow.net/questions/430153/how-to-construct-a-5-regular-1-planar-bipartite-graph.Lipton, M.; Mackall, E; Mattman, T. W.; Pierce, M.; Robinson, S.; Thomas, J.; and Weinschelbaum, I. "Six Variations on a Theme: Almost Planar Graphs." 5 Aug 2016. https://arxiv.org/abs/1608.01973.Pach, J. and Tóth. "Graphs Drawn With Few Crossing Per Edge." Combinatorica 17, 427-439, 1997.

请引用为

Weisstein, Eric W. “几乎平面图。” 来自 Web 资源。 https://mathworld.net.cn/AlmostPlanarGraph.html

主题分类