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,[1] Hadwiger's conjecture,[2] YΔY-reducible graphs,[3] and relations between treewidth and graph diameter.[4]
Characterization and recognition
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.[5]
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.[5][6]
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
Chromatic number
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.
Is every 6-vertex-connected K6-minor-free graph an apex graph?
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.[2] Jørgensen's conjecture remains unproven.[9] However, if false, it has only finitely many counterexamples.[10]
Local treewidth
A graph family F has bounded local treewidth if the graphs in F obey a functional relationship between
The concept of bounded local treewidth forms the basis of the theory of
Embeddings
If G is an apex graph with apex v, and τ is the minimum number of faces needed to cover all the neighbors of v in a planar embedding of G \ {v}, then G may be embedded onto a two-dimensional surface of
By using SPQR trees to encode the possible embeddings of the planar part of an apex graph, it is possible to compute a drawing of the graph in the plane in which the only crossings involve the apex vertex, minimizing the total number of crossings, in polynomial time.[15] However, if arbitrary crossings are allowed, it becomes NP-hard to minimize the number of crossings, even in the special case of apex graphs formed by adding a single edge to a planar graph.[16]
Apex graphs are also linklessly embeddable in three-dimensional space: they can be embedded in such a way that each cycle in the graph is the boundary of a disk that is not crossed by any other feature of the graph.[17] A drawing of this type may be obtained by drawing the planar part of the graph in a plane, placing the apex above the plane, and connecting the apex by straight-line edges to each of its neighbors. Linklessly embeddable graphs form a minor-closed family with the seven graphs in the Petersen family as their minimal forbidden minors;[1] therefore, these graphs are also forbidden as minors for the apex graphs. However, there exist linklessly embeddable graphs that are not apex graphs.
YΔY-reducibility
A connected graph is YΔY-reducible if it can be reduced to a single vertex by a sequence of steps, each of which is a Δ-Y or Y-Δ transform, the removal of a self-loop or multiple adjacency, the removal of a vertex with one neighbor, and the replacement of a vertex of degree two and its two neighboring edges by a single edge.[3]
Like the apex graphs and the linkless embeddable graphs, the YΔY-reducible graphs are closed under graph minors. And, like the linkless embeddable graphs, the YΔY-reducible graphs have the seven graphs in the Petersen family as forbidden minors, prompting the question of whether these are the only forbidden minors and whether the YΔY-reducible graphs are the same as the linkless embeddable graphs. However, Neil Robertson provided an example of an apex graph that is not YΔY-reducible. Since every apex graph is linkless embeddable, this shows that there are graphs that are linkless embeddable but not YΔY-reducible and therefore that there are additional forbidden minors for the YΔY-reducible graphs.[3]
Robertson's apex graph is shown in the figure. It can be obtained by connecting an apex vertex to each of the degree-three vertices of a rhombic dodecahedron, or by merging two diametrally opposed vertices of a four-dimensional hypercube graph. Because the rhombic dodecahedron's graph is planar, Robertson's graph is an apex graph. It is a triangle-free graph with minimum degree four, so it cannot be changed by any YΔY-reduction.[3]
Nearly planar graphs
If a graph is an apex graph, it is not necessarily the case that it has a unique apex. For instance, in the minor-minimal nonplanar graphs K5 and K3,3, any of the vertices can be chosen as the apex. Wagner (
However, the phrase "nearly planar graph" is highly ambiguous: it has also been used to refer to apex graphs,[18] graphs formed by adding one edge to a planar graph,[19] and graphs formed from a planar embedded graph by replacing a bounded number of faces by "vortexes" of bounded pathwidth,[20] as well as for other less precisely-defined sets of graphs.
Related graph classes
An abstract graph is said to be n-apex if it can be made planar by deleting n or fewer vertices. A 1-apex graph is also said to be apex.
According to Lipton et al. (2018), a graph is edge-apex if there is some edge in the graph that can be deleted to make the graph planar. A graph is contraction-apex if there is some edge in the graph that can be contracted to make the graph planar.
In general, if X is a class of graphs, an "apex-X" graph is a graph that can be brought into the class X by deleting some one vertex. For example, an apex-cograph is a graph G that has a vertex v such that G―v is a cograph.
See also
- Polyhedral pyramid, a 4-dimensional polytope whose vertices and edges form an apex graph, with the apex adjacent to every vertex of a polyhedral graph
Notes
- ^ a b Robertson, Seymour & Thomas (1993b).
- ^ a b Robertson, Seymour & Thomas (1993a).
- ^ a b c d Truemper (1992).
- ^ a b Eppstein (2000); Demaine & Hajiaghayi (2004).
- ^ a b Gupta & Impagliazzo (1991).
- ^ Pierce (2014).
- ^ Kawarabayashi (2009).
- ^ Lewis & Yannakakis (1980).
- ^ "Jorgensen's Conjecture", Open Problem Garden, retrieved 2016-11-13.
- ^ Kawarabayashi et al. (2012).
- ^ Eppstein (2000); Frick & Grohe (2001); Demaine & Hajiaghayi (2005).
- ^ Demaine, Hajiaghayi & Kawarabayashi (2009).
- ^ Grohe (2003).
- ^ Mohar (2001).
- ^ Chimani et al. (2009).
- ^ Cabello & Mohar (2010).
- ^ Robertson, Seymour & Thomas (1993c).
- ^ Robertson, Seymour & Thomas (1993c); Eppstein (2000).
- ^ Archdeacon & Bonnington (2004).
- ^ Abraham & Gavoille (2006).
References
- Abraham, Ittai; Gavoille, Cyril (2006), "Object location using path separators", S2CID 8844836.
- hdl:2292/5158.
- Cabello, Sergio; S2CID 17271180, archived from the original(PDF) on 2012-03-14, retrieved 2010-08-02.
- Chimani, Markus; Gutwenger, Carsten; Mutzel, Petra; Wolf, Christian (2009), "Inserting a vertex into a planar graph", Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA '09), pp. 375–383.
- S2CID 390856.
- Demaine, Erik D.; Hajiaghayi, Mohammad Taghi (2005), "Bidimensionality: new connections between FPT algorithms and PTASs", Proc. 16th ACM-SIAM Symposium on Discrete Algorithms (SODA '05), pp. 590–601, archived from the original on 2018-12-11, retrieved 2010-08-02.
- .
- S2CID 3172160.
- Frick, Markus; S2CID 999472.
- Grohe, Martin (2003), "Local tree-width, excluded minors, and approximation algorithms", S2CID 11751235.
- Gupta, A.; S2CID 209133.
- Jørgensen, Leif K. (1994), "Contractions to K8", Journal of Graph Theory, 18 (5): 431–448, ).
- S2CID 11647021.
- Kawarabayashi, Ken-ichi; Norine, Serguei; Thomas, Robin; Wollan, Paul (2012), minors in large 6-connected graphs, Bibcode:2012arXiv1203.2192K.
- Lewis, John M.; .
- Lipton, Max; Mackall, Eoin; Mattman, Thomas W.; Pierce, Mike; Robinson, Samantha; Thomas, Jeremy; Weinschelbaum, Ilan (2018), "Six variations on a theme: Almost planar graphs", Involve: A Journal of Mathematics, 11 (3): 413–448, S2CID 119740613.
- doi:10.1006/jctb.2000.2026, archived from the original(PDF) on 2017-09-22, retrieved 2010-08-02.
- Pierce, Mike (2014), Searching for and classifying the finite set of minor-minimal non-apex graphs (PDF), Honours thesis, California State University, Chico.
- S2CID 9608738.
- S2CID 1110662.
- Robertson, Neil; Seymour, Paul; Thomas, Robin (1993c), "A survey of linkless embeddings", in Robertson, Neil; Seymour, Paul (eds.), Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors (PDF), Contemporary Mathematics, vol. 147, American Mathematical Society, pp. 125–136.
- Truemper, Klaus (1992), Matroid Decomposition (PDF), Academic Press, pp. 100–101, archived from the original (PDF) on 2017-08-29, retrieved 2010-08-02.
- .
- .