主題
Search

1-平面圖


1-平面圖是一種可以在平面上繪製的圖,其中每條邊最多有一個交叉點,在該交叉點它與另一條邊交叉(Ringel 1965)。

具有 n 個頂點的 1-平面圖最多有 4n-8 條邊。這種最優的 1-平面圖已被完全表徵。

4-地圖圖 是 1-平面的。

Fabrici 和 Madaras (2007) 表明,1-平面圖具有最小頂點度 delta<=7,並且每個 3-連通的 1-平面圖都包含一條邊,其兩個端點的度數均至多為 20。

Borodin (1984) 證明了 1-平面圖是 6-可著色的(Fabrici 和 Madara 2007)。

1-平面繪製最多有 n-2 個交叉點。


另請參閱

2-平面圖單交叉圖

使用 探索

參考文獻

Borodin, O. V. "Solution of Ringel's Problems on the Vertex-Face Coloring of Plane Graphs and on the Coloring of 1-Planar Graphs." Diskret. Anal. Novosibirsk 41, 12-26, 1984.Brandenburg, F. J. "Straight-Line Drawings of 1-Planar Graphs." 2021 年 9 月 3 日。 https://arxiv.org/abs/2109.01692.Fabrici, I. and Madaras, T. "The Structure of 1-Planar Graphs." Disc. Math. 307, 854-865, 2007.Ringel, G. "Ein Sechsfarbenproblem auf der Kugel." Abh. Math. Sem. Univ. Hamburg 29, 107-117, 1965.

請引用為

Weisstein, Eric W. "1-平面圖。" 來自 Web 資源。 https://mathworld.tw/1-PlanarGraph.html