主題
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 定理, 環面圖, 三角剖分圖, 效用圖 在 課堂中探索此主題

在 中探索

參考文獻

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.

在 上被引用

平面圖

請引用為

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

主題分類