zbMATH — the first resource for mathematics

Graph minors. VII: Disjoint paths on a surface. (English) Zbl 0658.05044
[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.
Reviewer: F.Plastria

05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
68Q25 Analysis of algorithms and problem complexity
05C99 Graph theory
Full Text: DOI
[1] Kosniowski, C, ()
[2] Levine, H.I, Homotopic curves on surfaces, (), 986-990 · Zbl 0117.17104
[3] Robertson, N; Seymour, P.D, Graph minors. III. planar tree-width, J. combin. theory ser. B, 36, 49-64, (1984) · Zbl 0548.05025
[4] Robertson, N; Seymour, P.D, Graph minors. VI. disjoint paths across a disc, J. combin. theory ser. B, 41, 115-138, (1986) · Zbl 0598.05042
[5] {\scN. Robertson and P. D. Seymour}, Graph minors. VIII. A Kuratowski theorem for general surfaces, J. Combin. Theory Ser. B, to appear. · Zbl 0719.05033
[6] {\scN. Robertson and P. D. Seymour}, Graph minors. XIII. The disjoint paths problem, in preparation. · Zbl 0823.05038
[7] Schurle, A.W, ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.