主题
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-平面图单交叉图

使用 Wolfram|Alpha 探索

参考文献

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-平面图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/1-PlanarGraph.html