Edge-disjoint routing in plane switch graphs in linear time

By a switch graph we mean an undirected graph G=(P∪˙W,E) such that all vertices in P (the plugs) have degree one and all vertices in W (the switches) have even degrees. We call G plane if G is planar and can be embedded such that all plugs are in the outer face. Given a set (s₁,t₁), ..., (s_k,t_k) of pairs of plugs, the problem is to find edge-disjoint paths p₁, ..., p_k such that every p_i connects s_i with t_i. The best asymptotic worst case complexity known so far is quadratic in the number of vertices. A linear, and thus asymptotically optimal algorithm is introduced. This result may be viewed as a concluding “key-stone” for a number of previous results on various special cases of the problem