Quickly excluding a non-planar graph

2020/10/23 by Ken‐ichi Kawarabayashi, Kawarabayashi, Ken-ichi, Robin Thomas +3 · 4 citations
Computer Science · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Complexity and Algorithms in Graphs

paper · pdf · doi:10.48550/arxiv.2010.12397

Abstract

A cornerstone theorem in the Graph Minors series of Robertson and Seymour is the result that every graph G with no minor isomorphic to a fixed graph H has a certain structure. The structure can then be exploited to deduce far-reaching consequences. The exact statement requires some explanation, but roughly it says that there exist integers k,n depending on H only such that 0

Cited by

• Odd-Cycle-Packing-treewidth: On the Maximum Independent Set problem in odd-minor-free graph classes
• Two Disjoint Alternating Paths in Bipartite Graphs: Conformal Crosses
• Colorful Minors
• Catching Rats in H-minor-free Graphs

Related

• Forbidden minors: Finding the finite few
• On the excluded minor structure theorem for graphs of large treewidth
• Universal planar graphs for the topological minor relation
• Upper bounds on the graph minor theorem
• A short proof of the existence of a minor-universal countable planar graph