Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Apex graph
Summary
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 K_5 or K_3,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, Hadwiger's conjecture, YΔY-reducible graphs, and relations between treewidth and graph diameter.
Apex graphs are closed under the operation of taking minors: contracting any edge, or removing any edge or vertex, leads to another apex graph. For, if G is an apex graph with apex v, then any contraction or removal that does not involve v preserves the planarity of the remaining graph, as does any edge removal of an edge incident to v. If an edge incident to v is contracted, the effect on the remaining graph is equivalent to the removal of the other endpoint of the edge. And if v itself is removed, any other vertex may be chosen as the apex.
By the Robertson–Seymour theorem, because they form a minor-closed family of graphs, the apex graphs have a forbidden graph characterization.
There are only finitely many graphs that are neither apex graphs nor have another non-apex graph as a minor.
These graphs are forbidden minors for the property of being an apex graph.
Any other graph G is an apex graph if and only if none of the forbidden minors is a minor of G.
These forbidden minors include the seven graphs of the Petersen family, three disconnected graphs formed from the disjoint unions of two of K_5 and K_3,3, and many other graphs. However, a complete description of them remains unknown.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.