TOPICS
Search

Planar Straight Line Embedding


A planar straight line embedding of a planar graph is a planar embedding in which only straight line segments are used to connect the graph vertices. The Fáry theorem established that every planar graph has a planar straight line embedding with noncrossing edges (Bryant 1989; Skiena 1990, pp. 100 and 251; Scheinerman and Wilf 1994), and such embeddings (with rectilinear crossing number 0) are sometimes known as a Fáry embedding.

A planar straight line embedding of a planar graph can be constructed in the Wolfram Language using the "PlanarEmbedding" option to GraphLayout or in the Wolfram Language using PlanarGraph[g].

de Fraysseix et al. (1988) give an algorithm for constructing a planar straight line embedding for a planar graph of order n by placing the vertices on a (2n-4)×(n-2) grid (Skiena 1990, p. 251).


See also

Fáry Theorem, Graph Embedding, Planar Embedding, Planar Graph, Rectilinear Crossing Number, Straight Line Embedding

Explore with Wolfram|Alpha

References

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 139, 1976.Brandenburg, F. J. "Straight-Line Drawings of 1-Planar Graphs." 3 Sep 2021. https://arxiv.org/abs/2109.01692.Bryant, V. W. "Straight Line Representation of Planar Graphs." Elem. Math. 44, 64-66, 1989.de Fraysseix, H.; Pach, J; and Pollack, R. "Small Sets Supporting Fáry Embeddings of Planar Graphs." Proc. of the 20th Symposium on the Theory of Computing. ACM, pp. 426-433, 1988.Fáry, I. "On Straight Line Representations of Planar Graphs." Acta Sci. Math. (Szeged( 11, 229-233, 1948.Gross, J. T. and Yellen, J. Graph Theory and Its Applications. Boca Raton, FL: CRC Press, pp. 629 and 638, 1999.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. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 247, 2000.

Cite this as:

Weisstein, Eric W. "Planar Straight Line Embedding." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PlanarStraightLineEmbedding.html

Subject classifications