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.

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

##### MSC:

05C10 | Planar graphs; geometric and topological aspects of graph theory |

05C38 | Paths and cycles |

68Q25 | Analysis of algorithms and problem complexity |

05C99 | Graph theory |

##### Keywords:

graphs on surfaces; compact surface; forest; homoplasty; disjoint connecting paths; vertex-disjoint paths
PDF
BibTeX
XML
Cite

\textit{N. Robertson} and \textit{P. D. Seymour}, J. Comb. Theory, Ser. B 45, No. 2, 212--254 (1988; Zbl 0658.05044)

Full Text:
DOI

##### References:

[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.