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.
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).
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. Monthly101, 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.
by placing the vertices on a 
grid (Skiena 1990, p. 251).
