Graph minors. VII: Disjoint paths on a surface (Q1111568)

[For part VI see ibid. 41, 115-138 (1986; Zbl 0598.05042).] Continuing their series of nonconstructive proofs of polynomial solvability of problems, the authors here address the following ``homoplasty problem''. Let \(\Sigma\) be a compact surface, eventually with boundary. Two graphs in \(\Sigma\) are homoplastic iff there exists a homeomorphism of \(\Sigma\), leaving its boundary invariant, and transforming one into a graph which is pathwise homotopic to the other. The ``homoplasty problem'' is to decide whether for given graph G and forest H in \(\Sigma\) there exists a subgraph of G homoplastic to H. After proving several sufficient conditions for the homoplasty property to hold, mainly by way of geometric topology techniques, it is shown how these may be used to obtain a polynomial decision algorithm for the homoplasty problem for fixed surface \(\Sigma\) and forest H in \(\Sigma\). It then follows that for any surface \(\Sigma\) and integer k the following disjoint connecting paths problem is polynomially solvable: given a graph G in \(\Sigma\) and k pairs of vertices s(sub i), t(sub i) (1\(\leq i\leq k)\) of G, decide whether there exist k vertex-disjoint paths of G linking each of these pairs.