Rooted routing in the plane (Q1346696)

A partition \(P= \{P_ 1,\dots, P_ p\}\) of a set \(X\) of vertices of a graph \(G\) is realizable if there are vertex-disjoint trees \(T_ 1,\dots, T_ p\) in \(G\) such that \(P_ i\subseteq V(T_ i)\), for \(1\leq i\leq p\). A realization of \(P\) is such a set of trees. In this paper the author discusses a linear-time algorithm for instances of \(k\)-realizations (Input: a graph \(G\) and a set \(X\subseteq V(G)\) with \(| X|= k\). Question: which partitions of \(X\) are realizable in \(G\)?) where \(G\) is planar. The algorithm is due to \textit{B. A. Reed}, \textit{N. Robertson}, \textit{A. Schrijver} and \textit{P. D. Seymour} [Contemp. Math. 147, 295-301 (1993; Zbl 0791.05092)]. Also considered in the present paper are extensions to higher-genus surfaces and an algorithm of Robertson and Seymour for \(k\)-realizations in arbitrary graphs.