Apex Graph

An apex graph is a graph possessing at least one vertex whose removal results in a planar graph. The set of vertices whose removal results in a planar graph is known as the apices of the graph.

Planar graphs are threfore trivial apex graphs having all vertices as apices.

A nonplanar apex graph, sometimes also called a nearly planar graph (though this term is also used in other contexts), is a nonplanar graph possessing at least one vertex whose removal results in a planar graph.

Apex graphs differ from critical nonplanar 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.

There exist nonplanar apex graphs that are not singlecross graphs. For example, the complete bipartite graph K_(3,4) is nonplanar and apex but has graph crossing number 2.

Every apex graph has chromatic number <=5.


The numbers of apex graphs on n=1, 2, ... vertices are 1, 2, 4, 11, 34, 155, 1026, 11666, 226916, ... (OEIS A215620), while the numbers of nonplanar apex graphs are 0, 0, 0, 0, 1, 13, 204, 4700, 147063, ... (OEIS A215621), with the only nonplanar apex graph on n<=5 vertices being the complete graph K_5. The 13 nonplanar apex graphs on six vertices are illustrated above. In these graphs, the apices consist of all but 1 and 2 for the (6,5)-Turán graph, all but vertex 2 for the (6,132), (6,138), (6,148), and (5,1)-lollipop graphs, and all vertices for each of the others.

By the Robertson-Seymour theorem, since apex graphs are closed under minors, they have a finite obstruction set consisting of forbidden minors. The forbidden minors of apex graphs include the Petersen family graphs and the disjoint unions of 2K_5, K_5 union K_(3,3), and 2K_(3,3) (Pierce 2014, p. 8; Thomas 2014). Pierce (2014) identified 157 minimal apex-forbidden minors, but a complete list of forbidden minors is not yet known (Gupta and Impagliazzo 1991, Pierce 2014).

See also

Apex, Critical Nonplanar Graph, Graph Skewness, Planar Graph, Robertson's Apex Graph

Explore with Wolfram|Alpha


Gupta, A. and Impagliazzo, R. "Computing Planar Intertwines." In Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91). IEEE Computer Society, pp. 802-811, 1991.Pierce, M. "Searching for and Classifying the Finite Set of Minor-Minimal Non-Apex Graphs." Honours thesis. Chico, CA: California State University, Chico, 2014., N. J. A. Sequences A215620 and A215621 in "The On-Line Encyclopedia of Integer Sequences."Thomas, J. "Properties of 2-Connected MMNA Graphs." Preprint, 2014.

Cite this as:

Weisstein, Eric W. "Apex Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications