Explicit bounds for graph minors

2013/05/07 by Jim Geelen, Geelen, Jim, Tony Huynh +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #math.CO #msc:05C83

paper · pdf · doi:10.48550/arxiv.1305.1451

24 pages, 0 figures

arxiv created 2016/05/02 · arxiv updated 2016/05/03

Abstract

Let Σ be a surface with boundary b(Σ), L be a collection of k disjoint b(Σ)-paths in Σ, and P be a non-separating b(Σ)-path in Σ. We prove that there is a homeomorphism ϕ: Σ→ Σ that fixes each point of b(Σ) and such that ϕ(L) meets P at most 2k times. With this theorem, we derive explicit constants in the graph minor algorithms of Robertson and Seymour. We reprove a result concerning redundant vertices for graphs on surfaces, but with explicit bounds. That is, we prove that there exists a computable integer t:=t(Σ,k) such that if v is a 't-protected' vertex in a surface Σ, then v is redundant with respect to any k-linkage.

Cited by

• The price of homogeneity is polynomial

Related

• A single exponential bound for the redundant vertex Theorem on surfaces
• The Graph Minor Structure Theorem through Bidimensionality
• Optimal Bounds for the k-Disjoint Paths Problem
• A quasi-polynomial bound for the minimal excluded minors for a surface
• Minor-Universal Graph for Graphs on Surfaces