平面直线嵌入 -- 来自

平面直线嵌入

平面图的平面直线嵌入是一种平面嵌入，其中仅使用直线段连接图顶点。法里定理确立了每个平面图都具有带有非交叉边的平面直线嵌入（Bryant 1989；Skiena 1990，第 100 页和 251 页；Scheinerman 和 Wilf 1994），并且这种嵌入（直线交叉数为 0）有时被称为法里嵌入。

平面图的平面直线嵌入可以使用 Wolfram 语言中的"PlanarEmbedding"选项来GraphLayout或者在 Wolfram 语言中使用PlanarGraph[g]。

de Fraysseix等人（1988）给出了一个算法，用于构造阶数为的平面图的平面直线嵌入，方法是将顶点放置在网格上（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.net.cn/PlanarStraightLineEmbedding.html