Edge-disjoint routing in plane switch graphs in linear time. - Hochstein, J.M (Journal of the ACM)
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 (s1, t1), ?,(sk, tk) of pairs of plugs, the problem is to find edge-disjoint paths p1, ?, pk such that every pi connects si with ti. The best asymptotic worst-case complexity known so far is quadratic in the number of vertices. In this article, a linear, and thus asymptotically optimal, algorithm is introduced. This result may be viewed as a concluding "keystone" for a number of previous results on various special cases of the problem.