Graph minors, graphs on surfaces and networks

The main subject of our research will be the interplay of graph minors and connectivity. The main question which arises is the following: does a high enough connectivity of a graph, possibly applied together with some other topological conditions, guarantee the existence of a specified graph minor. One possible approach to this problem is the use of graphs embedded into surfaces and using conditions related to such an embedding. So far, we have been able to reduce several problems of this kind to finding a set of disjoint paths linking prescribed pairs of graph vertices. Such a theoretical problem has its real-life counterpart. Can pieces of information be sent across a (computer) network, so that their respective paths remain disjoint. We expect that techniques developed in the theoretical part of this project may be applied in the analysis and the design of algorithms for data flow in computer networks.