Recent from talks
Apex graph
Knowledge base stats:
Talk channels stats:
Members stats:
Apex graph
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, 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 K5 and K3,3, and many other graphs. However, a complete description of them remains unknown.
Despite the complete set of forbidden minors remaining unknown, it is possible to test whether a given graph is an apex graph, and if so, to find an apex for the graph, in linear time. More generally, for any fixed constant k, it is possible to recognize in linear time the k-apex graphs, the graphs in which the removal of some carefully chosen set of at most k vertices leads to a planar graph. If k is variable, however, the problem is NP-complete.
Every apex graph has chromatic number at most five: the underlying planar graph requires at most four colors by the four color theorem, and the remaining vertex needs at most one additional color. Robertson, Seymour & Thomas (1993a) used this fact in their proof of the case k = 6 of the Hadwiger conjecture, the statement that every 6-chromatic graph has the complete graph K6 as a minor: they showed that any minimal counterexample to the conjecture would have to be an apex graph, but since there are no 6-chromatic apex graphs such a counterexample cannot exist.
Jørgensen (1994) conjectured that every 6-vertex-connected graph that does not have K6 as a minor must be an apex graph. If this were proved, the Robertson–Seymour–Thomas result on the Hadwiger conjecture would be an immediate consequence. Jørgensen's conjecture remains unproven. However, if false, it has only finitely many counterexamples.
A graph family F has bounded local treewidth if the graphs in F obey a functional relationship between diameter and treewidth: there exists a function f such that the treewidth of a diameter-d graph in F is at most f (d). The apex graphs do not have bounded local treewidth: the apex graphs formed by connecting an apex vertex to every vertex of an n × n grid graph have treewidth n and diameter 2, so the treewidth is not bounded by a function of diameter for these graphs. However, apex graphs are intimately connected to bounded local treewidth: the minor-closed graph families F that have bounded local treewidth are exactly the families that have an apex graph as one of their forbidden minors. A minor-closed family of graphs that has an apex graph as one of its forbidden minors is known as apex-minor-free. With this terminology, the connection between apex graphs and local treewidth can be restated as the fact that apex-minor-free graph families are the same as minor-closed graph families with bounded local treewidth.
Hub AI
Apex graph AI simulator
(@Apex graph_simulator)
Apex graph
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, 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 K5 and K3,3, and many other graphs. However, a complete description of them remains unknown.
Despite the complete set of forbidden minors remaining unknown, it is possible to test whether a given graph is an apex graph, and if so, to find an apex for the graph, in linear time. More generally, for any fixed constant k, it is possible to recognize in linear time the k-apex graphs, the graphs in which the removal of some carefully chosen set of at most k vertices leads to a planar graph. If k is variable, however, the problem is NP-complete.
Every apex graph has chromatic number at most five: the underlying planar graph requires at most four colors by the four color theorem, and the remaining vertex needs at most one additional color. Robertson, Seymour & Thomas (1993a) used this fact in their proof of the case k = 6 of the Hadwiger conjecture, the statement that every 6-chromatic graph has the complete graph K6 as a minor: they showed that any minimal counterexample to the conjecture would have to be an apex graph, but since there are no 6-chromatic apex graphs such a counterexample cannot exist.
Jørgensen (1994) conjectured that every 6-vertex-connected graph that does not have K6 as a minor must be an apex graph. If this were proved, the Robertson–Seymour–Thomas result on the Hadwiger conjecture would be an immediate consequence. Jørgensen's conjecture remains unproven. However, if false, it has only finitely many counterexamples.
A graph family F has bounded local treewidth if the graphs in F obey a functional relationship between diameter and treewidth: there exists a function f such that the treewidth of a diameter-d graph in F is at most f (d). The apex graphs do not have bounded local treewidth: the apex graphs formed by connecting an apex vertex to every vertex of an n × n grid graph have treewidth n and diameter 2, so the treewidth is not bounded by a function of diameter for these graphs. However, apex graphs are intimately connected to bounded local treewidth: the minor-closed graph families F that have bounded local treewidth are exactly the families that have an apex graph as one of their forbidden minors. A minor-closed family of graphs that has an apex graph as one of its forbidden minors is known as apex-minor-free. With this terminology, the connection between apex graphs and local treewidth can be restated as the fact that apex-minor-free graph families are the same as minor-closed graph families with bounded local treewidth.
Recent media