主題
Search

區域性交叉數


區域性交叉數定義為最小的非負整數 k,使得該圖具有一個 k-平面圖繪製。換句話說,它是圖中單條邊在所有可能的圖繪製中被交叉的最小次數。Guy et al. (1968) 將此定義歸功於 Ringel 未發表的工作。

圖的區域性交叉數也被 Thomassen (1988) 稱為交叉指標,有時也稱為交叉引數 (Schaefer 2013),但 Schaefer (2013) 強烈建議使用“區域性交叉數”。然而,“平面性”一詞可能更具描述性且更簡潔。

Schaefer (2014) 以及 Ábrego 和 Fernández-Merchant (2017) 將圖 G 的區域性交叉數表示為 lcr(G)

根據 布魯克斯定理圖的厚度 至多比區域性交叉數大一 (Kainen 1973, Thomassen 1988)。

區域性交叉數為 0 的圖等價於 平面圖。一般來說,k-平面圖 的區域性交叉數可以是 0, 1, ..., 或 k

LocalCrossingNumberExamples

由於 希伍德圖完全圖 K_6非平面圖,但如上所示,它們具有區域性交叉數為 1 的嵌入,因此它們是 1-平面圖

區域性交叉數為 1 的圖類(即,1-平面圖 但不是 平面圖 的圖)包括 國王圖林德格倫-蘇塞利耶圖

交叉十二面體圖 的區域性交叉數為 2。

完全圖 K_n圖交叉數 的最佳已知界限 (De Klerk et al. 2007) 給出了局部交叉數的界限為

 lcr(K_n)>=(n^2)/(18.62)+Theta(n)

(Ábrego 和 Fernández-Merchant 2017)。

區域性交叉數限制為直線邊的版本被稱為 直線區域性交叉數


另請參閱

圖交叉數, k-平面圖, 直線區域性交叉數

使用 探索

參考文獻

Ábrego, B. M. 和 Fernández-Merchant, S. "The Rectilinear Local Crossing Number of K_n." J. Combin. Th. Ser. A 151, 131-145, 2017.de Klerk, E.; Pasechnik, D. V.; 和 Schrijver, A. "Reduction of Symmetric Semidefinite Programs Using the Regular *-Representation." Math. Program. 109, 613-624, 2007.Guy, R. .K; Jenkyns, T.; 和 Schaer, J. "The Toroidal Crossing Number of the Complete Graph." J. Combin. Th. 4, 376-390, 1968.Kainen, P. C. "Thickness and Coarseness of Graphs." Abh. Math. Semin. Univ. Hamburg 39, 88-95, 1973.Ringel, G. "Ein Sechsfarbenproblem auf der Kugel." Abh. Math. Sem. Univ. Hamburg 29, 107-117, 1965.Schaefer, M. "The Graph Crossing Number and Its Variants: A Survey." Electron. J. Combin., DS21, pp. 43-45, May 15, 2013.Thomassen, C. "Rectilinear Drawings of Graphs." J. Graph Th. 12, 335-341, 1988.

引用此頁

Weisstein, Eric W. "區域性交叉數。" 來自 Web 資源。 https://mathworld.tw/LocalCrossingNumber.html

學科分類