Summary: We develop new structural results for apex-minor-free graphs and show their power by developing two new approximation algorithms. The first is an additive approximation for coloring within 2 of the optimal chromatic number, which is essentially best possible, and generalizes the seminal result by C. Thomassen [J. Comb. Theory, Ser. B 70, No. 1, 67–100 (1997; Zbl 0883.05051)] for bounded-genus graphs. This result also improves our understanding from an algorithmic point of view of the venerable Hadwiger conjecture about coloring \(H\)-minor-free graphs. The second approximation result is a PTAS for unweighted TSP in apex-minor-free graphs, which generalizes PTASs for TSP in planar graphs and bounded-genus graphs.
We strengthen the structural results from the seminal graph minor theory of Robertson and Seymour in the case of apex-minor-free graphs, showing that apices can be made adjacent only to vortices if we generalize the notion of vortices to “quasivortices” of bounded treewidth, proving a conjecture from [E. D. Demaine and M. Hajiaghayi, “Equivalence of local treewidth and linear local treewidth and its algorithmic applications”, in: Proceedings of the 15th annual ACM-SIAM symposium on discrete algorithms, SODA ’04, 840–849 (2004)]. We show that this structure theorem is a powerful tool for developing algorithms on apex-minor-free graphs, including for the classic problems of coloring and TSP. In particular, we use this theorem to partition the edges of a graph into \(k\) pieces, for any \(k\), such that contracting any piece results in a bounded-treewidth graph, generalizing previous similar results for planar graphs and bounded-genus graphs. We also highlight the difficulties in extending our results to general \(H\)-minor-free graphs.
For the entire collection see [Zbl 1166.68001].