TOPICS
Search

Fáry Theorem

Fáry's theorem states that every finite graph that is simple and planar admits a planar straight line embedding, in which edges are straight line segments meeting only at common endpoints.

More strongly, every prescribed planar graph embedding of such a graph has an equivalent planar straight line embedding. The redrawing preserves the embedding, including the cyclic order of incident edges at each graph vertex and the chosen outer graph face, but may change the graph vertex coordinates (Erickson 2023).

The theorem was independently proved by Steinitz and Rademacher (1934), Wagner (1936), Fáry (1948), and Stein (1951).

See also

Planar Graph, Planar Straight Line Embedding, Steinitz's Theorem

Explore with Wolfram|Alpha

References

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.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 Representation of Planar Graphs." Acta Sci. Math. (Szeged) 11, 229-233, 1948.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, pp. 100 and 251, 1990.Stein, S. K. "Convex Maps." Proc. Amer. Math. Soc. 2, 464-466, 1951.Steinitz, E. and Rademacher, H. Vorlesungen über die Theorie der Polyeder. Berlin, Germany: Julius Springer, 1934.Wagner, K. "Bemerkungen zum Vierfarbenproblem." Jahresber. Deutschen Math.Verein. 46, 26-32, 1936.

Referenced on Wolfram|Alpha

Fáry Theorem

Cite this as:

Weisstein, Eric W. "Fáry Theorem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/FaryTheorem.html

Subject classifications