Lukas' Notes

graph-theory

Definition

Fáry's Theorem

Fáry’s theorem states that every graph that admits a plane drawing with edges represented as curves also admits a plane drawing with edges represented as straight-line segments.

Equivalently, every planar graph has a crossing-free straight-line drawing.

Intuition

Straightening

A curved plane drawing already fixes the combinatorial structure of the drawing: it determines which vertices, edges, and faces touch each other. Fáry’s theorem says that the curves are not essential to this structure.

The drawing can be adjusted so that each face has enough geometric room for its boundary edges to be made straight. The important point is not the exact shape of each curve, but the fact that the curves do not cross.

Thus curved edges are useful for thinking about planarity, but they do not give extra drawing power over straight-line segments.