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. Fáry (1948) showed 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  by placing the vertices on a  grid (Skiena 1990, p. 251).

REFERENCES

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 139, 1976.

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.