主题
Search

平面图


PlanarGraphs

如果一个可以绘制在平面上而没有图的边交叉(即,它的图的交叉数为 0),则该图是平面的。具有 n=1, 2, ... 个节点的平面图的数量分别为 1, 2, 4, 11, 33, 142, 822, 6966, 79853, ... (OEIS A005470; Wilson 1975, p. 162),其中前几个如图所示。

PlanarConnectedGraphs

对应的平面连通图的数量分别为 1, 1, 1, 2, 6, 20, 99, 646, 5974, 71885, ... (OEIS A003094; Steinbach 1990, p. 131)

对于图的交叉数为 1 的图,似乎没有标准使用的术语。特别是,术语“几乎平面”和“1-平面”在文献中用于其他概念(例如,Karpov 2013)。因此,在这项工作中,术语单交叉图被引入来表示这种图。交叉(或直线交叉)数为 0 的图根据定义是平面的,交叉(或直线交叉)数为 1 的图被称为单交叉图,而交叉(或直线交叉)数为 2 的图被称为双交叉图。

PlanarGraphEmbeddings

请注意,虽然图的平面性是图的内在属性,但有时仍然可以绘制平面图的非平面嵌入。例如,上面的两个嵌入都对应于平面四面体图,但左侧的嵌入是平面的,而右侧的嵌入不是。

平面图的平面嵌入有时被称为平面嵌入或平面图 (Harborth and Möller 1994)。法里定理指出,任何简单平面图都可以绘制成平面直线嵌入平面直线嵌入可以使用 Wolfram 语言 中的以下命令生成:PlanarGraph[g].

有许多用于平面性测试的高效算法,其中大多数算法基于 Auslander 和 Parter 的 o(n^3) 算法 (1961; Skiena 1990, p. 247)。可以使用 Wolfram 语言 中的命令测试图的平面性:PlanarGraphQ[g].

一个图是平面的当且仅当它有一个组合对偶图 (Harary 1994, p. 115)。任何平面图都有一个图嵌入,即平面直线嵌入,其中边不相交 (Fáry 1948; Bryant 1989; Skiena 1990, pp. 100 and 251; Scheinerman and Wilf 1994)。

只有平面图才有对偶图。如果一个有限简单图 G 是平面的,那么 G 至少有一个顶点度 <=5。如果图 G 及其图的补图 G* 都是平面的,那么 G 最多有八个顶点。

完全图仅在 n<=4 时是平面的。完全二部图 K_(3,3) 是非平面的。更一般地,Kuratowski 在 1930 年证明,一个图是平面的当且仅当它不包含任何完全图 K_5K_(3,3) 的图扩展。

有许多度量标准用于表征图偏离平面性的程度,其中包括图的交叉数直线交叉数图的偏斜度图的粗糙度图的厚度

厚度为 1 的图是平面的,而图的厚度为 1 或 2 的图被称为双平面图。非平面顶点图是一个非平面图,它至少有一个顶点,移除该顶点后会得到一个平面图。

所有都是平面的,环图网格图轮图也是如此。每个九个顶点的平面图都有一个非平面补图 (Battle et al. 1962; Skiena 1990, p. 250)。

下表给出了最小度数至少为 k 的平面图的数量。

kOEISn=1, 2, 3, ...
2A0493700, 0, 1, 3, 10, 50, 335, ...
3A0493710, 0, 0, 1, 2, 9, 46, 386, ...
4A0493720, 0, 0, 0, 0, 1, 1, 4, 14, 69, ...
5A0493730, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 5, ...

另请参阅

顶点图, Barnette 猜想, 双平面图, 完全图, 临界非平面图, 双环面图, 双交叉图, 对偶图, 法里定理, 图的交叉数, 图的亏格, 图的偏斜度, 图的厚度, 整数嵌入, Kuratowski 约简定理, 非平面图, 外平面图, 平面连通图, 平面嵌入, 平面直线嵌入, 多面体图, 直线交叉数, 单交叉图, Steinitz 定理, 环面图, 三角剖分图, 效用图 在 MathWorld 课堂中探索此主题

在 Wolfram|Alpha 中探索

参考文献

Auslander, L. and Parter, S. "On Imbedding Graphs in the Sphere." J. Math. Mechanics 10, 517-523, 1961.Battle, J.; Harary, F.; and Kodama, Y. "Every Planar Graph with Nine Points has a Nonplanar Complement." Bull. Amer. Math. Soc. 68, 569-571, 1962.Booth, K. S. and Lueker, G. S. "Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity using PQ-Tree Algorithms." J. Comput. System Sci. 13, 335-379, 1976.Bryant, V. W. "Straight Line Representation of Planar Graphs." Elem. Math. 44, 64-66, 1989.Cai, J.; Han, X.; and Tarjan, R. "New Solutions to Four Planar Graph Problems." Technical Report. New York University, 1990.Di Battista, G.; Eades, P.; Tamassia, R.; and Tollis, I. G. Graph Drawing: Algorithms for the Visualization of Graphs. Englewood Cliffs, NJ: Prentice-Hall, 1998.Eades, P. and Tamassia, R. "Algorithms for Drawing Graphs: An Annotated Bibliography." Technical Report CS-89-09. Department of Computer Science. Providence, RI: Brown University, Feb. 1989.Eppstein, D. "Layered Graph Drawing." http://www.ics.uci.edu/~eppstein/junkyard/thickness/.Even, S. Graph Algorithms. Rockville, MD: Computer Science Press, 1979.Fáry, I. "On Straight Line Representations of Planar Graphs." Acta Sci. Math. (Szeged( 11, 229-233, 1948.Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 91-94, 1984.Harary, F. "Planarity." Ch. 11 in Graph Theory. Reading, MA: Addison-Wesley, pp. 102-125, 1994.Harborth, H. and Möller, M. "Minimum Integral Drawings of the Platonic Graphs." Math. Mag. 67, 355-358, 1994.Hopcroft, J. and Tarjan, R. "Efficiency Planarity Testing." J. ACM 21, 549-568, 1974.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.Kocay, W. and Pantel, C. "An Algorithm for Finding a Planar Layout of a Graph with a Regular Polygon as Outer Face." Util. Math. 48, 161-178, 1995.Le Lionnais, F. Les nombres remarquables. Paris: Hermann, p. 56, 1983.Nishizeki, T. and Rahman, M. S. Planar Graph Drawing. Singapore: World Scientific, 2004.Read, R. C. "A New Method for Drawing a Planar Graph Given the Cyclic Order of the Edges at Each Vertex." Congr. Numer. 56, 31-44, 1987.Scheinerman, E. and Wilf, H. S. "The Rectilinear Crossing Number of a Complete Graph and Sylvester's 'Four Point' Problem of Geometric Probability." Amer. Math. Monthly 101, 939-943, 1994.Skiena, S. "Planar Graphs." §6.5 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 247-253, 1990.Sloane, N. J. A. Sequences A003094/M1652, A005470/M1252, A049370, A049371, A049372, and A049373 in "The On-Line Encyclopedia of Integer Sequences."Steinbach, P. Field Guide to Simple Graphs. Albuquerque, NM: Design Lab, 1990.Stony Brook Algorithm Repository. §1.4.12. "Planarity Detection and Embedding." http://www.cs.sunysb.edu/~algorith/files/planar-drawing.shtml.Wagon, S. "Coloring Planar Maps and Graphs." Ch. 24 in Mathematica in Action, 2nd ed. New York: Springer-Verlag, pp. 507-537, 1999.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 243, 2000.Whitney, H. "Non-Separable and Planar Graphs." Trans. Amer. Math. Soc. 34, 339-362, 1932.Whitney, H. "Planar Graphs." Fund. Math. 21, 73-84, 1933.Wilson, R. J. Introduction to Graph Theory. London: Longman, 1975.

在 Wolfram|Alpha 上被引用

平面图

请引用为

Weisstein, Eric W. "平面图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/PlanarGraph.html

主题分类