Fáry's theorem

Fáry's theorem, also known as Wagner's theorem or the Fáry-Wagner theorem, states that any simple planar graph can be drawn in the plane in such a way that its edges are straight line segments and no edges cross. In other words, every planar graph admits a straight-line embedding.

Details:

The theorem guarantees the existence of a straight-line embedding, but it doesn't provide a simple algorithm for finding one. The existence of such an embedding contrasts with some non-planar graphs, which cannot be drawn without edge crossings regardless of how the edges are drawn.

The theorem applies only to simple planar graphs, meaning that there are no parallel edges (multiple edges connecting the same pair of vertices) or self-loops (edges connecting a vertex to itself). Such features would trivially cause issues with straight-line embeddings.

History:

The theorem was independently proven by István Fáry in 1948, Klaus Wagner in 1936, and D. O. Woodall in 1969. Because of its independent discoveries, it is often referred to by different names. Fáry's proof is the most widely recognized, hence the most common name.

Implications:

Fáry's theorem is significant because it simplifies the problem of drawing planar graphs. Instead of having to consider arbitrary curves for edges, one only needs to consider straight line segments. This has implications for graph drawing algorithms and graph visualization.

Related Concepts:

• Planar Graph: A graph that can be drawn in the plane without any edges crossing.
• Graph Embedding: A mapping of the vertices and edges of a graph onto a surface, such as the plane.
• Straight-line embedding: A graph embedding where all edges are represented by straight line segments.