TOPICS
Search

Critical Nonplanar Graph


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

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"].

CriticalNonplanarGraph

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


See also

Apex Graph, Nonplanar Graph, Planar Graph, Triangulated Graph

Explore with Wolfram|Alpha

References

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.

Referenced on Wolfram|Alpha

Critical Nonplanar Graph

Cite this as:

Weisstein, Eric W. "Critical Nonplanar Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CriticalNonplanarGraph.html

Subject classifications