Graph minors. VI. Disjoint paths across a disc (Q1079580): Difference between revisions

[For part V see the authors' paper ibid. 41, 92-114 (1986; Zbl 0598.05055).] Given a graph G and a finite set of pairs of vertices, do there exist vertex-disjoint paths joining each pair? This decision problem, DISJOINT CONNECTING PATHS, is known to be NP-complete, even for planar graphs. In this paper it is shown to be polynomial in two special cases: when G is drawn either on a disc or on a cylinder, all specified vertices always lying on the boundary. In fact the authors derive a structural characterization, leading to a polynomial algorithm, for the more general DISJOINT CONNECTING SUBGRAPHS problem. Here pairs of vertices are replaced by pairwise disjoint subsets of vertices, and it is asked to decide whether a forest may be found in G with these subsets as vertex sets of its subtrees. Fundamentally the method on the disk relies on several reduction steps, which usually reduce the number of vertices of the base graph, and, when these no longer apply, a move to some dual graph, permitting further reductions. In the cylindrical case the question reduces to the analogous one of finding a set of disjoint links between both boundaries, having a prespecified winding number. This is solved by the explicit construction of the set of realizable winding numbers.