Define planar graph.

A planar graph is a graph that can be drawn on a plane (or a sphere) without any of its edges crossing. This means that the vertices (nodes) and edges can be represented in such a way that no two edges intersect except at their common endpoints.

Key characteristics of a planar graph include:

• It can be embedded in a plane without edge crossings.
• It satisfies Euler’s formula for connected planar graphs: V − E + F = 2, where V is the number of vertices, E is the number of edges, and F is the number of faces (including the outer, infinite face).
• A graph is planar if and only if it does not contain a subgraph that is a K₅ (complete graph on five vertices) or a K₃,₃ (complete bipartite graph on six vertices, split into two sets of three).

Examples include trees, cycles, and graphs with no K₅ or K₃,₃ substructures. Non-planar graphs, such as K₅ or K₃,₃, cannot be drawn without edge crossings.