Graph minors. VII: Disjoint paths on a surface (Q1111568)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Graph minors. VII: Disjoint paths on a surface |
scientific article |
Statements
Graph minors. VII: Disjoint paths on a surface (English)
0 references
1988
0 references
[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.
0 references
graphs on surfaces
0 references
compact surface
0 references
forest
0 references
homoplasty
0 references
disjoint connecting paths
0 references
vertex-disjoint paths
0 references