In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K5 or K3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.
Apex graphs are closed under the operation of taking minors and play a role in several other aspects of graph minor theory: linkless embedding,[1] Hadwiger's conjecture,[2] YΔY-reducible graphs,[3] and relations between treewidth and graph diameter.[4]
- ^ Cite error: The named reference
linklesswas invoked but never defined (see the help page). - ^ Robertson, Seymour & Thomas (1993a).
- ^ Cite error: The named reference
t92was invoked but never defined (see the help page). - ^ Cite error: The named reference
localwas invoked but never defined (see the help page).