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
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    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
    0 references