Approximations for the disjoint paths problem in high-diameter planar networks

We consider the problem of connecting distinguished terminal pairs in a graph via edgedisjoint paths. This is a classical NP-complete problem for which no general approximation techniques are known; it has recently been brought into focus in papers discussing applications to admission control in high-speed networks and to routing in all-optical networks. In this paper we provide O(logn)-approximation algorithms for two natural optimization versions of this problem for the class of nearly-Eulerian, uniformly high-diameter planar graphs, which includes two-dimensional meshes and other common planar interconnection networks. We give an O(logn)-approximation to the maximum number of terminal pairs that can be simultaneously connected via edge-disjoint paths, and an O(logn)-approximation to the minimum number of wavelengths needed to route a collection of terminal pairs in the “optical routing” model considered by Raghavan and Upfal, and others. The latter result improves on an O(log n)-approximation for the special case of the mesh obtained independently by Aumann and Rabani. For both problems the O(logn)-approximation is a consequence of an O(1)-approximation for the special case when all terminal pairs are roughly the same distance apart. Our algorithms make use of a number of new techniques, including the construction of a “crossbar” structure in any nearly-Eulerian planar graph, and develops some connections with classical matroid algorithms.