Planar graph

A graph that can be drawn in the plane with edges intersecting only at shared endpoints. Such a drawing is a plane embedding, and its regions are called faces.

Graph (discrete mathematics): A mathematical structure consisting of vertices connected by edges. Planarity is a property of graphs, defined by whether their vertices and edges admit a suitable drawing.
Kuratowski's theorem: A finite graph is planar exactly when it contains no subdivision of K₅ or K₃,₃. It characterizes nonplanarity through two minimal obstruction patterns.
Graph drawing: The visualization of a graph by points for vertices and curves for edges. Planarity is a central constraint in drawings that avoid edge crossings.
Nonplanar graph: A graph that cannot be drawn in the plane without edges crossing away from shared endpoints. It is the direct opposite of a planar graph.
Plane graph: A graph together with a particular embedding in the plane, including its faces. Unlike a planar graph, a plane graph includes the specific crossing-free drawing.
Wagner's theorem: A finite graph is planar exactly when neither K₅ nor K₃,₃ is its minor. It gives a minor-based characterization parallel to Kuratowski’s subdivision criterion.
Printed circuit board: A board that connects electronic components through conductive tracks and layers. Single-layer routing is closely tied to embedding a circuit graph without crossings.
Crossing number: The minimum number of edge crossings in any drawing of a graph in the plane. It measures how far a nonplanar graph is from a crossing-free drawing.
Face (planar graph): A connected region of the plane left after a plane graph is drawn. Faces are the regions whose number is constrained by Euler’s formula.
K₅: The complete graph on five vertices, with an edge between every pair of vertices. It is one of the two fundamental nonplanar obstructions.

Linked from 37 pages