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 Sep 2018 |
Externally published | Yes |
Keywords
- Graphs
- Linkages
- Minors
- Surfaces