主題
Search

平面直線嵌入

平面圖的平面直線嵌入是一種平面嵌入，其中僅使用直線段連線圖頂點。法裡定理確立了每個平面圖都具有帶有非交叉邊的平面直線嵌入（Bryant 1989；Skiena 1990，第 100 頁和 251 頁；Scheinerman 和 Wilf 1994），並且這種嵌入（直線交叉數為 0）有時被稱為法裡嵌入。

平面圖的平面直線嵌入可以使用 Wolfram 語言 中的"PlanarEmbedding"選項來GraphLayout或者在 Wolfram 語言 中使用PlanarGraph[g]。

de Fraysseix等人（1988）給出了一個演算法，用於構造階數為 n 的平面圖的平面直線嵌入，方法是將頂點放置在 (2n-4)×(n-2) 網格上（Skiena 1990，第 251 頁）。

另請參閱

法裡定理, 圖嵌入, 平面嵌入, 平面圖, 直線交叉數, 直線嵌入

使用 探索

參考文獻

Bondy, J. A. 和 Murty, U. S. R. 圖論及其應用。 New York: North Holland, p. 139, 1976.Brandenburg, F. J. "1-平面圖的直線繪圖。" 2021 年 9 月 3 日。 https://arxiv.org/abs/2109.01692.Bryant, V. W. "平面圖的直線表示。" Elem. Math. 44, 64-66, 1989.de Fraysseix, H.; Pach, J; 和 Pollack, R. "支援平面圖法裡嵌入的小集合。" Proc. of the 20th Symposium on the Theory of Computing. ACM, pp. 426-433, 1988.Fáry, I. "關於平面圖的直線表示。" Acta Sci. Math. (Szeged( 11, 229-233, 1948.Gross, J. T. 和 Yellen, J. 圖論及其應用。 Boca Raton, FL: CRC Press, pp. 629 和 638, 1999.Scheinerman, E. 和 Wilf, H. S. "完全圖的直線交叉數和西爾維斯特的“四點”幾何機率問題。" Amer. Math. Monthly 101, 939-943, 1994.Skiena, S. 實現離散數學：使用 Mathematica 的組合數學和圖論。 Reading, MA: Addison-Wesley, 1990.West, D. B. 圖論導論，第 2 版。 Englewood Cliffs, NJ: Prentice-Hall, p. 247, 2000.

請引用為

Weisstein, Eric W. "平面直線嵌入。" 來自 Web 資源。 https://mathworld.tw/PlanarStraightLineEmbedding.html

主題分類