主題
Search

單交叉圖


對於圖交叉數 (graph crossing number) 為 1 的圖,似乎沒有標準術語。特別是,術語“近乎平面圖 (almost planar graph)” (例如,Karpov 2013) 和 1-平面圖 (1-planar graph) (例如,Fabrici 和 Madaras 2007,Brandenburg 2021) 在文獻中用於不同的概念。因此,在這項工作中,術語“單交叉圖 (singlecross graph)” 用於指代圖交叉數為 1 的圖。

莫比烏斯梯 (Möbius ladders) 透過構造是單交叉圖。

使用以下演算法可以很容易地檢查圖是否為單交叉圖 (M. Haythorpe,私人通訊,2019 年 4 月 16 日)。首先,確認該圖是非平面的。然後,對於所有非相鄰的邊對 (a,b)(c,d),刪除這兩條邊並建立一個新頂點 v。最後,檢查透過新增邊 (a,v), (b,v), (c,v), 和 (d,v) 中的任何一條邊而獲得的四個新圖中的任何一個是否是平面的。如果是,則原始圖是單交叉圖。

節點數為 n=1 的單交叉簡單圖的數量為 0, 0, 0, 0, 1, 12, 162, 3183, 74696, 1892122, ... (A307071),連通圖的數量為 0, 0, 0, 0, 1, 11, 149, 3008, 71335, 1814021, ... (A307072)。


另請參閱

1-平面圖, 頂點圖, 臨界非平面圖, 雙交叉圖, 圖交叉數, 平面圖, 直線交叉數

使用 探索

參考文獻

Brandenburg, F. J. "Straight-Line Drawings of 1-Planar Graphs." 3 Sep 2021. https://arxiv.org/abs/2109.01692.Fabrici, I. and Madaras, T. "the Structure of 1-Planar Graphs." Disc. Math. 307, 854-865, 2007.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.Sloane, N. J. A. Sequences A307071 and A in "The On-Line Encyclopedia of Integer Sequences."

請引用為

Weisstein, Eric W. "Singlecross Graph." 來自 Web 資源。 https://mathworld.tw/SinglecrossGraph.html

主題分類