Explicit bounds for graph minors

Abstract

Let $\Sigma$ be a surface with boundary $b(\Sigma )$, $\mathcal{L}$ be a collection of $k$ disjoint $b(\Sigma )$-paths in $\Sigma$, and $P$ be a non-separating $b(\Sigma )$-path in $\Sigma$. We prove that there is a homeomorphism $\varphi :\Sigma \to \Sigma$ that fixes each point of $b(\Sigma )$ and such that $\varphi (\mathcal{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(\Sigma ,k)$ such that if $v$ is a '$t$-protected' vertex in a surface $\Sigma$, then $v$ is redundant with respect to any $k$-linkage.

24 pages, 0 figures