The excluded minor structure theorem with planarly embedded wall

2009/09/23 by Bojan Mohar, Mohar, Bojan
Computer Science · Mathematics · #05C83 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.0909.4329

openalex publication_date 2009/09/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A graph is nearly embedded in a surface if it consists of graph G₀ that is embedded in the surface, together with a bounded number of vortices having no large transactions. It is shown that every large wall (or grid minor) in a nearly embedded graph, many rows of which intersect the embedded subgraph G₀ of the near-embedding, contains a large subwall that is planarly embedded within G₀. This result provides some hidden details needed for a strong version of the Robertson and Seymour's excluded minor theorem as presented in [K. Kawarabayashi, B. Mohar, Some recent progress and applications in graph minor theory, Graphs Combin. 23 (2007) 1-46].

Related

• The Local Structure Theorem for Graph Minors with Finite Index
• A New Proof of the Flat Wall Theorem
• A grid theorem for strong immersions of walls
• On the excluded minor structure theorem for graphs of large treewidth
• A quasi-polynomial bound for the minimal excluded minors for a surface