Edge-disjoint routing in plane switch graphs in linear time
By a switch graph, we mean an undirected graph G = (P boolean OR 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.
edge-disjoint paths algorithms planar graphs theory