planar graph


Definition: A graph that can be drawn in the plane with no crossing edges.

Generalization (I am a kind of ...)

Specialization (... is a kind of me.)
dual, planar straight-line graph.

Note: Equivalently, a graph that does not contain any subgraph homeomorphic to the complete graph on 5 vertices or the complete bipartite graph with 3 vertices in each partition.

Author: JLG


draw a graph in the plane such that no edges cross (C, C++, Java, and Mathematica).
Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 12 August 2019.
HTML page formatted Mon Aug 12 09:59:40 2019.

Cite this as:
Joseph L. Ganley, "planar graph", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 12 August 2019. (accessed TODAY) Available from: