## Abstract

Let Σ be a surface with boundary bd(Σ), L be a collection of k disjoint bd(Σ)-paths in Σ, and P be a non-separating bd(Σ)-path in Σ. We prove that there is a homeomorphism ϕ:Σ→Σ that fixes each point of bd(Σ) 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 (1995) [10]. 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.

Original language | English |
---|---|

Pages (from-to) | 80-106 |

Number of pages | 27 |

Journal | Journal of Combinatorial Theory, Series B |

Volume | 132 |

DOIs | |

Publication status | Published - 1 Sept 2018 |

Externally published | Yes |

## Keywords

- Graphs
- Linkages
- Minors
- Surfaces