A nonplanar graph is said to be critical nonplanar if the removal of a vertex
results in a planar graph for every vertex
of .

Critical nonplanar graphs differ from apex graphs in that an apex graph requires only that there exist at
least one vertex whose removal gives a planar graph,
while a critical nonplanar graph requires that removal of each vertex gives
a planar graph.

Classes of graphs that are critically nonplanar include the Möbius
ladder.

Critical nonplanar graphs are implemented in the Wolfram
Language as GraphData["CriticalNonplanar"].

The numbers of critical nonplanar simple graphs on , 2, ... nodes are 0, 0, 0, 0, 1, 8, 40, 258, ... (OEIS A158922), the first few of which are illustrated
above.

Sloane, N. J. A. Sequence A158922 in "The On-Line Encyclopedia of Integer Sequences."Tucker,
A. Applied
Combinatorics, 4th ed. New York: Wiley, p. 43, 2001.