maximal planar graph

maximal planar graph

[′mak·sə·məl ¦plān·ər ‚graf] (mathematics) A planar graph to which no new arcs can be added without forcing crossings and hence violating planarity.