TOPICS
Search

Planar Straight-Line Embedding

A planar straight-line embedding of a planar graph is a planar graph embedding whose edges are straight line segments meeting only at common endpoints. The common-endpoint condition distinguishes a planar straight-line embedding from a general straight-line drawing, whose edges may have other intersections. The Fáry theorem establishes that every finite graph that is simple and planar has a planar straight-line embedding (Bryant 1989; Skiena 1990, pp. 100 and 251; Scheinerman and Wilf 1994), and these embeddings, which have rectilinear crossing number 0, are sometimes known as Fáry embeddings.

Every prescribed planar graph embedding of a finite graph that is simple has an equivalent planar straight-line embedding. This redrawing preserves the embedding, including its rotation system and chosen outer graph face, while allowing graph vertex coordinates to change (Erickson 2023).

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 simple planar graph of vertex count n>=3 by placing the vertices on a (2n-4)×(n-2) grid (Skiena 1990, p. 251).

See also

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

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.Erickson, J. "Straight-Line Planar Maps." One-Dimensional Computational Topology course notes. 2023. https://jeffe.cs.illinois.edu/teaching/comptop/2023/notes/11-straight-line-planar.html.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 Resource. https://mathworld.wolfram.com/PlanarStraight-LineEmbedding.html

Subject classifications