Edge-disjoint routing in plane switch graphs in linear time
Jan M. Hochstein, Karsten Weihe · Journal of the ACM · 2004
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 1 , t 1 ), …,( s k , t k ) of pairs of plugs, the problem is to find edge-disjoint paths p 1 , …, 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. 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.