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.
de Fraysseix et al. (1988) give an algorithm for constructing a planar straight line embedding for a simpleplanar
graph of vertex count 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.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. 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).
