Disjoint Paths in Densely Embedded Graphs

We consider the following maximum disjoint paths problem (mdpp). We are given a large network, and pairs of nodes that wish to communicate over paths through the network -- the goal is to simultaneously connect as many of these pairs as possible in such a way that no two communication paths share an edge in the network. This classical problem has been brought into focus recently in papers discussing applications to routing in high-speed networks, where the current lack of understanding of the MDPP is an obstacle to the design of practical heuristics. W