主題
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.tw/AlmostPlanarGraph.html

主題分類