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 K₅ 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.

An apex graph. The subgraph formed by removing the red vertex is planar.

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 K₅ and K_3,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 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.[7] If k is variable, however, the problem is NP-complete.[8]

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 K₆ 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.

Unsolved problem in mathematics: Is every 6-vertex-connected ${\displaystyle K_{6}}$-minor-free graph an apex graph? (more unsolved problems in mathematics)

Jørgensen (1994) conjectured that every 6-vertex-connected graph that does not have K₆ 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 diameter and treewidth: there exists a function ƒ such that the treewidth of a diameter-d graph in F is at most ƒ(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.[4] 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.

The concept of bounded local treewidth forms the basis of the theory of bidimensionality, and allows for many algorithmic problems on apex-minor-free graphs to be solved exactly by a polynomial-time algorithm or a fixed-parameter tractable algorithm, or approximated using a polynomial-time approximation scheme.[11] Apex-minor-free graph families obey a strengthened version of the graph structure theorem, leading to additional approximation algorithms for graph coloring and the travelling salesman problem.[12] However, some of these results can also be extended to arbitrary minor-closed graph families via structure theorems relating them to apex-minor-free graphs.[13]

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 genus τ − 1: simply add that number of bridges to the planar embedding, connecting together all the faces into which v must be connected. For instance, adding a single vertex to an outerplanar graph (a graph with τ = 1) produces a planar graph. When G\{v} is 3-connected, his bound is within a constant factor of optimal: every surface embedding of G requires genus at least τ/160. However, it is NP-hard to determine the optimal genus of a surface embedding of an apex graph.[14]

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

Robertson's example of a non-YΔY-reducible apex graph.

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

The 16-vertex Möbius ladder, an example of a nearly planar graph.

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 K₅ and K_3,3, any of the vertices can be chosen as the apex. Wagner (1967, 1970) defined a nearly planar graph to be a nonplanar apex graph with the property that all vertices can be the apex of the graph; thus, K₅ and K_3,3 are nearly planar. He provided a classification of these graphs into four subsets, one of which consists of the graphs that (like the Möbius ladders) can be embedded onto the Möbius strip in such a way that the single edge of the strip coincides with a Hamiltonian cycle of the graph. Prior to the proof of the four color theorem, he proved that every nearly planar graph can be colored with at most four colors, except for the graphs formed from a wheel graph with an odd outer cycle by replacing the hub vertex with two adjacent vertices, which require five colors. Additionally, he proved that, with a single exception (the eight-vertex complement graph of the cube) every nearly planar graph has an embedding onto the projective plane.

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. (2016) harvtxt error: no target: CITEREFLiptonMackallMattmanPierce2016 (help), 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.

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

1. Robertson, Seymour & Thomas (1993b).
2. Robertson, Seymour & Thomas (1993a).
3. Truemper (1992).
4. Eppstein (2000); Demaine & Hajiaghayi (2004).
5. Gupta & Impagliazzo (1991).
6. Pierce (2014).
7. Kawarabayashi (2009).
8. Lewis & Yannakakis (1980).
9. "Jorgensen's Conjecture", Open Problem Garden, retrieved 2016-11-13.
10. Kawarabayashi et al. (2012).
11. Eppstein (2000); Frick & Grohe (2001); Demaine & Hajiaghayi (2005).
12. Demaine, Hajiaghayi & Kawarabayashi (2009).
13. Grohe (2003).
14. Mohar (2001).
15. Chimani et al. (2009).
16. Cabello & Mohar (2010).
17. Robertson, Seymour & Thomas (1993c).
18. Robertson, Seymour & Thomas (1993c); Eppstein (2000).
19. Archdeacon & Bonnington (2004).
20. Abraham & Gavoille (2006).

References

• Abraham, Ittai; Gavoille, Cyril (2006), "Object location using path separators", Proc. 25th ACM Symposium on Principles of Distributed Computing (PODC '06), pp. 188–197, doi:10.1145/1146381.1146411.
• Archdeacon, Dan; Bonnington, C.P.C. Paul (2004), "Obstructions for embedding cubic graphs on the spindle surface", Journal of Combinatorial Theory, Series B, 91 (2): 229–252, doi:10.1016/j.jctb.2004.02.001.
• Cabello, Sergio; Mohar, Bojan (2010), "Adding one edge to planar graphs makes crossing number hard", Proc. 26th ACM Symposium on Computational Geometry (SoCG '10) (PDF), pp. 68–76, doi:10.1145/1810959.1810972, 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.
• Demaine, Erik D.; Hajiaghayi, Mohammad Taghi (2004), "Diameter and treewidth in minor-closed graph families, revisited", Algorithmica, 40 (3): 211–215, doi:10.1007/s00453-004-1106-1.
• 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.
• Demaine, Erik D.; Hajiaghayi, Mohammad Taghi; Kawarabayashi, Ken-ichi (2009), "Approximation algorithms via structural results for apex-minor-free graphs" (PDF), Proc. 36th International Colloquium Automata, Languages and Programming (ICALP '09), Lecture Notes in Computer Science, 5555, Springer-Verlag, pp. 316–327, doi:10.1007/978-3-642-02927-1_27.
• Eppstein, David (2000), "Diameter and treewidth in minor-closed graph families", Algorithmica, 27 (3): 275–291, arXiv:math.CO/9907126, doi:10.1007/s004530010020.
• Frick, Markus; Grohe, Martin (2001), "Deciding first-order properties of locally tree-decomposable structures", Journal of the ACM, 48 (6): 1184–1206, arXiv:cs/0004007, doi:10.1145/504794.504798.
• Grohe, Martin (2003), "Local tree-width, excluded minors, and approximation algorithms", Combinatorica, 23 (4): 613–632, arXiv:math.CO/0001128, doi:10.1007/s00493-003-0037-9.
• Gupta, A.; Impagliazzo, R. (1991), "Computing planar intertwines", Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91), IEEE Computer Society, pp. 802–811, doi:10.1109/SFCS.1991.185452.
• Jørgensen, Leif K. (1994), "Contractions to K₈", Journal of Graph Theory, 18 (5): 431–448, doi:10.1002/jgt.3190180502. As cited by Robertson, Seymour, and Thomas (1993a, 1993c).
• Kawarabayashi, Ken-ichi (2009), "Planarity allowing few error vertices in linear time" (PDF), Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS '09), IEEE Computer Society, pp. 639–648, doi:10.1109/FOCS.2009.45.
• Kawarabayashi, Ken-ichi; Norine, Serguei; Thomas, Robin; Wollan, Paul (2012), ${\displaystyle K_{6}}$ minors in large 6-connected graphs, arXiv:1203.2192, Bibcode:2012arXiv1203.2192K.
• Lewis, John M.; Yannakakis, Mihalis (1980), "The node-deletion problem for hereditary properties is NP-complete", Journal of Computer and System Sciences, 20 (2): 219–230, doi:10.1016/0022-0000(80)90060-4.
• 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, arXiv:1608.01973, doi:10.2140/involve.2018.11.413.
• Mohar, Bojan (2001), "Face covers and the genus problem for apex graphs" (PDF), Journal of Combinatorial Theory, Series B, 82 (1): 102–117, 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.
• Robertson, Neil; Seymour, Paul; Thomas, Robin (1993a), "Hadwiger's conjecture for K₆-free graphs" (PDF), Combinatorica, 13 (3): 279–361, doi:10.1007/BF01202354.
• Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993b), "Linkless embeddings of graphs in 3-space", Bulletin of the American Mathematical Society, 28 (1): 84–89, arXiv:math/9301216, doi:10.1090/S0273-0979-1993-00335-5, MR 1164063.
• 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, 147, American Mathematical Society, pp. 125–136.
• Truemper, Klaus (1992), Matroid Decomposition (PDF), Academic Press, pp. 100–101.
• Wagner, Klaus (1967), "Fastplättbare Graphen", Journal of Combinatorial Theory (in German), 3 (4): 326–365, doi:10.1016/S0021-9800(67)80103-0.
• Wagner, Klaus (1970), "Zum basisproblem der nicht in die projektive ebene einbettbaren graphen, I", Journal of Combinatorial Theory (in German), 9 (1): 27–43, doi:10.1016/S0021-9800(70)80052-7.