Fáry's theorem

Every simple planar graph has a planar drawing in which each edge is a straight line segment, with no crossings between edges.

Planar graph: A graph that can be drawn in the plane with no edges crossing except at shared endpoints. Fáry's theorem begins with this topological condition and guarantees a straight-line drawing.
Graph theory: The mathematical study of vertices, edges, and the structures formed by their connections. Fáry's theorem concerns how graph connectivity can be represented geometrically.
István Fáry: A Hungarian mathematician whose work included the theorem that bears his name on straight-line drawings of planar graphs. His 1948 paper established the result now commonly called Fáry's theorem.
Graph drawing: The representation of a graph by points for vertices and curves or segments for edges. Fáry's theorem guarantees that planar graphs admit a particularly simple kind of graph drawing.
Steinitz's theorem: A characterization stating that the graphs of three-dimensional convex polytopes are exactly the 3-connected planar graphs. It links planarity to convex geometric realizations, a stronger structure than straight edges alone.
Planar embedding: A specification of a graph's drawing on a surface, including the cyclic order of edges around each vertex. The theorem can preserve an embedding while replacing curved edges with straight segments.
Simple graph: A graph with no loops and no multiple edges between the same pair of vertices. The theorem's standard statement assumes this restriction on the graph.
Klaus Wagner: A German mathematician known for foundational work in graph theory, including a contemporaneous straight-line drawing result. Wagner independently obtained the theorem around the same period as Fáry.
Planar graph drawing algorithms: Algorithms that place planar graph vertices and edges in the plane without crossings. The theorem provides the existence guarantee these algorithms turn into explicit layouts.
Book embedding: A graph drawing with vertices on a spine and edges assigned to pages, where edges on each page do not cross. It imposes a different geometric layout model than the planar straight-line drawings guaranteed here.

Linked from 1 page